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