1   /*
2    * @(#)Permuter.java    1.8 04/07/26
3    * 
4    * Copyright (c) 2004 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.8 04/07/26
39   */
40  
41  
42  
43  import java.util.Random;
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.8 07/26/04
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();
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[] 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