KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > Permuter


1 /*
2  * @(#)Permuter.java 1.9 05/11/17
3  *
4  * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions are met:
8  *
9  * -Redistribution of source code must retain the above copyright notice, this
10  * list of conditions and the following disclaimer.
11  *
12  * -Redistribution in binary form must reproduce the above copyright notice,
13  * this list of conditions and the following disclaimer in the documentation
14  * and/or other materials provided with the distribution.
15  *
16  * Neither the name of Sun Microsystems, Inc. or the names of contributors may
17  * be used to endorse or promote products derived from this software without
18  * specific prior written permission.
19  *
20  * This software is provided "AS IS," without a warranty of any kind. ALL
21  * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, INCLUDING
22  * ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE
23  * OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN MIDROSYSTEMS, INC. ("SUN")
24  * AND ITS LICENSORS SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE
25  * AS A RESULT OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS
26  * DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR ANY LOST
27  * REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL,
28  * INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY
29  * OF LIABILITY, ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE,
30  * EVEN IF SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
31  *
32  * You acknowledge that this software is not designed, licensed or intended
33  * for use in the design, construction, operation or maintenance of any
34  * nuclear facility.
35  */
36
37 /*
38  * @(#)Permuter.java 1.9 05/11/17
39  */
40
41
42
43 import java.util.Random JavaDoc;
44
45 /**
46  * An object that implements a cheesy pseudorandom permutation of the integers
47  * from zero to some user-specified value. (The permutation is a linear
48  * function.)
49  *
50  * @version 1.9 11/17/05
51  * @author Josh Bloch
52  */
53 class Permuter {
54     /**
55      * The size of the permutation.
56      */
57     private int modulus;
58
59     /**
60      * Nonnegative integer less than n that is relatively prime to m.
61      */
62     private int multiplier;
63
64     /**
65      * Pseudorandom nonnegative integer less than n.
66      */
67     private int addend = 22;
68
69     public Permuter(int n) {
70         if (n<0) {
71             throw new IllegalArgumentException JavaDoc();
72     }
73         modulus = n;
74         if (n==1) {
75             return;
76     }
77
78         // Initialize the multiplier and offset
79 multiplier = (int) Math.sqrt(n);
80         while (gcd(multiplier, n) != 1) {
81             if (++multiplier == n) {
82                 multiplier = 1;
83         }
84     }
85     }
86
87     /**
88      * Returns the integer to which this permuter maps the specified integer.
89      * The specified integer must be between 0 and n-1, and the returned
90      * integer will be as well.
91      */
92     public int map(int i) {
93         return (multiplier * i + addend) % modulus;
94     }
95
96     /**
97      * Calculate GCD of a and b, which are assumed to be non-negative.
98      */
99     private static int gcd(int a, int b) {
100         while(b != 0) {
101             int tmp = a % b;
102             a = b;
103             b = tmp;
104         }
105         return a;
106     }
107
108     /**
109      * Simple test. Takes modulus on command line and prints out permutation.
110      */
111     public static void main(String JavaDoc[] args) {
112         int modulus = Integer.parseInt(args[0]);
113         Permuter p = new Permuter(modulus);
114         for (int i=0; i<modulus; i++) {
115             System.out.print(p.map(i)+" ");
116     }
117         System.out.println();
118     }
119 }
120
121
Popular Tags