View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  
18  package org.apache.commons.math.random;
19  
20  import java.io.Serializable;
21  import java.security.MessageDigest;
22  import java.security.SecureRandom;
23  import java.security.NoSuchAlgorithmException;
24  import java.security.NoSuchProviderException;
25  import java.util.Collection;
26  
27  import org.apache.commons.math.MathRuntimeException;
28  import org.apache.commons.math.util.MathUtils;
29  
30  /**
31   * Implements the {@link RandomData} interface using a {@link RandomGenerator}
32   * instance to generate non-secure data and a {@link java.security.SecureRandom}
33   * instance to provide data for the <code>nextSecureXxx</code> methods. If no
34   * <code>RandomGenerator</code> is provided in the constructor, the default is
35   * to use a generator based on {@link java.util.Random}. To plug in a different
36   * implementation, either implement <code>RandomGenerator</code> directly or
37   * extend {@link AbstractRandomGenerator}.
38   * <p>
39   * Supports reseeding the underlying pseudo-random number generator (PRNG). The
40   * <code>SecurityProvider</code> and <code>Algorithm</code> used by the
41   * <code>SecureRandom</code> instance can also be reset.
42   * </p>
43   * <p>
44   * For details on the default PRNGs, see {@link java.util.Random} and
45   * {@link java.security.SecureRandom}.
46   * </p>
47   * <p>
48   * <strong>Usage Notes</strong>:
49   * <ul>
50   * <li>
51   * Instance variables are used to maintain <code>RandomGenerator</code> and
52   * <code>SecureRandom</code> instances used in data generation. Therefore, to
53   * generate a random sequence of values or strings, you should use just
54   * <strong>one</strong> <code>RandomDataImpl</code> instance repeatedly.</li>
55   * <li>
56   * The "secure" methods are *much* slower. These should be used only when a
57   * cryptographically secure random sequence is required. A secure random
58   * sequence is a sequence of pseudo-random values which, in addition to being
59   * well-dispersed (so no subsequence of values is an any more likely than other
60   * subsequence of the the same length), also has the additional property that
61   * knowledge of values generated up to any point in the sequence does not make
62   * it any easier to predict subsequent values.</li>
63   * <li>
64   * When a new <code>RandomDataImpl</code> is created, the underlying random
65   * number generators are <strong>not</strong> intialized. If you do not
66   * explicitly seed the default non-secure generator, it is seeded with the
67   * current time in milliseconds on first use. The same holds for the secure
68   * generator. If you provide a <code>RandomGenerator</code> to the constructor,
69   * however, this generator is not reseeded by the constructor nor is it reseeded
70   * on first use.</li>
71   * <li>
72   * The <code>reSeed</code> and <code>reSeedSecure</code> methods delegate to the
73   * corresponding methods on the underlying <code>RandomGenerator</code> and
74   * <code>SecureRandom</code> instances. Therefore, <code>reSeed(long)</code>
75   * fully resets the initial state of the non-secure random number generator (so
76   * that reseeding with a specific value always results in the same subsequent
77   * random sequence); whereas reSeedSecure(long) does <strong>not</strong>
78   * reinitialize the secure random number generator (so secure sequences started
79   * with calls to reseedSecure(long) won't be identical).</li>
80   * <li>
81   * This implementation is not synchronized.
82   * </ul>
83   * </p>
84   * 
85   * @version $Revision: 772119 $ $Date: 2009-05-06 05:43:28 -0400 (Wed, 06 May 2009) $
86   */
87  public class RandomDataImpl implements RandomData, Serializable {
88  
89      /** Serializable version identifier */
90      private static final long serialVersionUID = -626730818244969716L;
91  
92      /** underlying random number generator */
93      private RandomGenerator rand = null;
94  
95      /** underlying secure random number generator */
96      private SecureRandom secRand = null;
97  
98      /**
99       * Construct a RandomDataImpl.
100      */
101     public RandomDataImpl() {
102     }
103 
104     /**
105      * Construct a RandomDataImpl using the supplied {@link RandomGenerator} as
106      * the source of (non-secure) random data.
107      * 
108      * @param rand
109      *            the source of (non-secure) random data
110      * @since 1.1
111      */
112     public RandomDataImpl(RandomGenerator rand) {
113         super();
114         this.rand = rand;
115     }
116 
117     /**
118      * {@inheritDoc}
119      * <p>
120      * <strong>Algorithm Description:</strong> hex strings are generated using a
121      * 2-step process.
122      * <ol>
123      * <li>
124      * len/2+1 binary bytes are generated using the underlying Random</li>
125      * <li>
126      * Each binary byte is translated into 2 hex digits</li>
127      * </ol>
128      * </p>
129      * 
130      * @param len
131      *            the desired string length.
132      * @return the random string.
133      */
134     public String nextHexString(int len) {
135         if (len <= 0) {
136             throw MathRuntimeException.createIllegalArgumentException(
137                   "length must be positive ({0})", len);
138         }
139 
140         // Get a random number generator
141         RandomGenerator ran = getRan();
142 
143         // Initialize output buffer
144         StringBuffer outBuffer = new StringBuffer();
145 
146         // Get int(len/2)+1 random bytes
147         byte[] randomBytes = new byte[(len / 2) + 1];
148         ran.nextBytes(randomBytes);
149 
150         // Convert each byte to 2 hex digits
151         for (int i = 0; i < randomBytes.length; i++) {
152             Integer c = Integer.valueOf(randomBytes[i]);
153 
154             /*
155              * Add 128 to byte value to make interval 0-255 before doing hex
156              * conversion. This guarantees <= 2 hex digits from toHexString()
157              * toHexString would otherwise add 2^32 to negative arguments.
158              */
159             String hex = Integer.toHexString(c.intValue() + 128);
160 
161             // Make sure we add 2 hex digits for each byte
162             if (hex.length() == 1) {
163                 hex = "0" + hex;
164             }
165             outBuffer.append(hex);
166         }
167         return outBuffer.toString().substring(0, len);
168     }
169 
170     /**
171      * Generate a random int value uniformly distributed between
172      * <code>lower</code> and <code>upper</code>, inclusive.
173      * 
174      * @param lower
175      *            the lower bound.
176      * @param upper
177      *            the upper bound.
178      * @return the random integer.
179      */
180     public int nextInt(int lower, int upper) {
181         if (lower >= upper) {
182             throw MathRuntimeException.createIllegalArgumentException(
183                     "upper bound ({0}) must be greater than lower bound ({1})",
184                     upper, lower);
185         }
186         RandomGenerator rand = getRan();
187         double r = rand.nextDouble();
188         return (int) ((r * upper) + ((1.0 - r) * lower) + r);
189     }
190 
191     /**
192      * Generate a random long value uniformly distributed between
193      * <code>lower</code> and <code>upper</code>, inclusive.
194      * 
195      * @param lower
196      *            the lower bound.
197      * @param upper
198      *            the upper bound.
199      * @return the random integer.
200      */
201     public long nextLong(long lower, long upper) {
202         if (lower >= upper) {
203             throw MathRuntimeException.createIllegalArgumentException(
204                   "upper bound ({0}) must be greater than lower bound ({1})",
205                   upper, lower);
206         }
207         RandomGenerator rand = getRan();
208         double r = rand.nextDouble();
209         return (long) ((r * upper) + ((1.0 - r) * lower) + r);
210     }
211 
212     /**
213      * {@inheritDoc}
214      * <p>
215      * <strong>Algorithm Description:</strong> hex strings are generated in
216      * 40-byte segments using a 3-step process.
217      * <ol>
218      * <li>
219      * 20 random bytes are generated using the underlying
220      * <code>SecureRandom</code>.</li>
221      * <li>
222      * SHA-1 hash is applied to yield a 20-byte binary digest.</li>
223      * <li>
224      * Each byte of the binary digest is converted to 2 hex digits.</li>
225      * </ol>
226      * </p>
227      * 
228      * @param len
229      *            the length of the generated string
230      * @return the random string
231      */
232     public String nextSecureHexString(int len) {
233         if (len <= 0) {
234             throw MathRuntimeException.createIllegalArgumentException(
235                   "length must be positive ({0})", len);
236         }
237 
238         // Get SecureRandom and setup Digest provider
239         SecureRandom secRan = getSecRan();
240         MessageDigest alg = null;
241         try {
242             alg = MessageDigest.getInstance("SHA-1");
243         } catch (NoSuchAlgorithmException ex) {
244             return null; // gulp FIXME? -- this *should* never fail.
245         }
246         alg.reset();
247 
248         // Compute number of iterations required (40 bytes each)
249         int numIter = (len / 40) + 1;
250 
251         StringBuffer outBuffer = new StringBuffer();
252         for (int iter = 1; iter < numIter + 1; iter++) {
253             byte[] randomBytes = new byte[40];
254             secRan.nextBytes(randomBytes);
255             alg.update(randomBytes);
256 
257             // Compute hash -- will create 20-byte binary hash
258             byte hash[] = alg.digest();
259 
260             // Loop over the hash, converting each byte to 2 hex digits
261             for (int i = 0; i < hash.length; i++) {
262                 Integer c = Integer.valueOf(hash[i]);
263 
264                 /*
265                  * Add 128 to byte value to make interval 0-255 This guarantees
266                  * <= 2 hex digits from toHexString() toHexString would
267                  * otherwise add 2^32 to negative arguments
268                  */
269                 String hex = Integer.toHexString(c.intValue() + 128);
270 
271                 // Keep strings uniform length -- guarantees 40 bytes
272                 if (hex.length() == 1) {
273                     hex = "0" + hex;
274                 }
275                 outBuffer.append(hex);
276             }
277         }
278         return outBuffer.toString().substring(0, len);
279     }
280 
281     /**
282      * Generate a random int value uniformly distributed between
283      * <code>lower</code> and <code>upper</code>, inclusive. This algorithm uses
284      * a secure random number generator.
285      * 
286      * @param lower
287      *            the lower bound.
288      * @param upper
289      *            the upper bound.
290      * @return the random integer.
291      */
292     public int nextSecureInt(int lower, int upper) {
293         if (lower >= upper) {
294             throw MathRuntimeException.createIllegalArgumentException(
295                   "upper bound ({0}) must be greater than lower bound ({1})",
296                   upper, lower);
297         }
298         SecureRandom sec = getSecRan();
299         return lower + (int) (sec.nextDouble() * (upper - lower + 1));
300     }
301 
302     /**
303      * Generate a random long value uniformly distributed between
304      * <code>lower</code> and <code>upper</code>, inclusive. This algorithm uses
305      * a secure random number generator.
306      * 
307      * @param lower
308      *            the lower bound.
309      * @param upper
310      *            the upper bound.
311      * @return the random integer.
312      */
313     public long nextSecureLong(long lower, long upper) {
314         if (lower >= upper) {
315             throw MathRuntimeException.createIllegalArgumentException(
316                   "upper bound ({0}) must be greater than lower bound ({1})",
317                   upper, lower);
318         }
319         SecureRandom sec = getSecRan();
320         return lower + (long) (sec.nextDouble() * (upper - lower + 1));
321     }
322 
323     /**
324      * {@inheritDoc}
325      * <p>
326      * <strong>Algorithm Description</strong>: For small means, uses simulation
327      * of a Poisson process using Uniform deviates, as described <a
328      * href="http://irmi.epfl.ch/cmos/Pmmi/interactive/rng7.htm"> here.</a>
329      * </p>
330      * <p>
331      * The Poisson process (and hence value returned) is bounded by 1000 * mean.
332      * </p>
333      * 
334      * <p>
335      * For large means, uses a reject method as described in <a
336      * href="http://cg.scs.carleton.ca/~luc/rnbookindex.html">Non-Uniform Random
337      * Variate Generation</a>
338      * </p>
339      * 
340      * <p>
341      * References:
342      * <ul>
343      * <li>Devroye, Luc. (1986). <i>Non-Uniform Random Variate Generation</i>.
344      * New York, NY. Springer-Verlag</li>
345      * </ul>
346      * </p>
347      * 
348      * @param mean
349      *            mean of the Poisson distribution.
350      * @return the random Poisson value.
351      */
352     public long nextPoisson(double mean) {
353         if (mean <= 0) {
354             throw MathRuntimeException.createIllegalArgumentException(
355                   "the Poisson mean must be positive ({0})", mean);
356         }
357 
358         RandomGenerator rand = getRan();
359 
360         double pivot = 6.0;
361         if (mean < pivot) {
362             double p = Math.exp(-mean);
363             long n = 0;
364             double r = 1.0d;
365             double rnd = 1.0d;
366 
367             while (n < 1000 * mean) {
368                 rnd = rand.nextDouble();
369                 r = r * rnd;
370                 if (r >= p) {
371                     n++;
372                 } else {
373                     return n;
374                 }
375             }
376             return n;
377         } else {
378             double mu = Math.floor(mean);
379             double delta = Math.floor(pivot + (mu - pivot) / 2.0); // integer
380             // between 6
381             // and mean
382             double mu2delta = 2.0 * mu + delta;
383             double muDeltaHalf = mu + delta / 2.0;
384             double logMeanMu = Math.log(mean / mu);
385 
386             double muFactorialLog = MathUtils.factorialLog((int) mu);
387 
388             double c1 = Math.sqrt(Math.PI * mu / 2.0);
389             double c2 = c1 +
390                         Math.sqrt(Math.PI * muDeltaHalf /
391                                   (2.0 * Math.exp(1.0 / mu2delta)));
392             double c3 = c2 + 2.0;
393             double c4 = c3 + Math.exp(1.0 / 78.0);
394             double c = c4 + 2.0 / delta * mu2delta *
395                        Math.exp(-delta / mu2delta * (1.0 + delta / 2.0));
396 
397             double y = 0.0;
398             double x = 0.0;
399             double w = Double.POSITIVE_INFINITY;
400 
401             boolean accept = false;
402             while (!accept) {
403                 double u = nextUniform(0.0, c);
404                 double e = nextExponential(mean);
405 
406                 if (u <= c1) {
407                     double z = nextGaussian(0.0, 1.0);
408                     y = -Math.abs(z) * Math.sqrt(mu) - 1.0;
409                     x = Math.floor(y);
410                     w = -z * z / 2.0 - e - x * logMeanMu;
411                     if (x < -mu) {
412                         w = Double.POSITIVE_INFINITY;
413                     }
414                 } else if (c1 < u && u <= c2) {
415                     double z = nextGaussian(0.0, 1.0);
416                     y = 1.0 + Math.abs(z) * Math.sqrt(muDeltaHalf);
417                     x = Math.ceil(y);
418                     w = (-y * y + 2.0 * y) / mu2delta - e - x * logMeanMu;
419                     if (x > delta) {
420                         w = Double.POSITIVE_INFINITY;
421                     }
422                 } else if (c2 < u && u <= c3) {
423                     x = 0.0;
424                     w = -e;
425                 } else if (c3 < u && u <= c4) {
426                     x = 1.0;
427                     w = -e - logMeanMu;
428                 } else if (c4 < u) {
429                     double v = nextExponential(mean);
430                     y = delta + v * 2.0 / delta * mu2delta;
431                     x = Math.ceil(y);
432                     w = -delta / mu2delta * (1.0 + y / 2.0) - e - x * logMeanMu;
433                 }
434                 accept = (w <= x * Math.log(mu) -
435                          MathUtils.factorialLog((int) (mu + x)) /
436                          muFactorialLog);
437             }
438             // cast to long is acceptable because both x and mu are whole
439             // numbers.
440             return (long) (x + mu);
441         }
442     }
443 
444     /**
445      * Generate a random value from a Normal (a.k.a. Gaussian) distribution with
446      * the given mean, <code>mu</code> and the given standard deviation,
447      * <code>sigma</code>.
448      * 
449      * @param mu
450      *            the mean of the distribution
451      * @param sigma
452      *            the standard deviation of the distribution
453      * @return the random Normal value
454      */
455     public double nextGaussian(double mu, double sigma) {
456         if (sigma <= 0) {
457             throw MathRuntimeException.createIllegalArgumentException(
458                   "standard deviation must be positive ({0})", sigma);
459         }
460         RandomGenerator rand = getRan();
461         return sigma * rand.nextGaussian() + mu;
462     }
463 
464     /**
465      * Returns a random value from an Exponential distribution with the given
466      * mean.
467      * <p>
468      * <strong>Algorithm Description</strong>: Uses the <a
469      * href="http://www.jesus.ox.ac.uk/~clifford/a5/chap1/node5.html"> Inversion
470      * Method</a> to generate exponentially distributed random values from
471      * uniform deviates.
472      * </p>
473      * 
474      * @param mean
475      *            the mean of the distribution
476      * @return the random Exponential value
477      */
478     public double nextExponential(double mean) {
479         if (mean < 0.0) {
480             throw MathRuntimeException.createIllegalArgumentException(
481                   "mean must be positive ({0})", mean);
482         }
483         RandomGenerator rand = getRan();
484         double unif = rand.nextDouble();
485         while (unif == 0.0d) {
486             unif = rand.nextDouble();
487         }
488         return -mean * Math.log(unif);
489     }
490 
491     /**
492      * {@inheritDoc}
493      * <p>
494      * <strong>Algorithm Description</strong>: scales the output of
495      * Random.nextDouble(), but rejects 0 values (i.e., will generate another
496      * random double if Random.nextDouble() returns 0). This is necessary to
497      * provide a symmetric output interval (both endpoints excluded).
498      * </p>
499      * 
500      * @param lower
501      *            the lower bound.
502      * @param upper
503      *            the upper bound.
504      * @return a uniformly distributed random value from the interval (lower,
505      *         upper)
506      */
507     public double nextUniform(double lower, double upper) {
508         if (lower >= upper) {
509             throw MathRuntimeException.createIllegalArgumentException(
510                   "upper bound ({0}) must be greater than lower bound ({1})",
511                   upper, lower);
512         }
513         RandomGenerator rand = getRan();
514 
515         // ensure nextDouble() isn't 0.0
516         double u = rand.nextDouble();
517         while (u <= 0.0) {
518             u = rand.nextDouble();
519         }
520 
521         return lower + u * (upper - lower);
522     }
523 
524     /**
525      * Returns the RandomGenerator used to generate non-secure random data.
526      * <p>
527      * Creates and initializes a default generator if null.
528      * </p>
529      * 
530      * @return the Random used to generate random data
531      * @since 1.1
532      */
533     private RandomGenerator getRan() {
534         if (rand == null) {
535             rand = new JDKRandomGenerator();
536             rand.setSeed(System.currentTimeMillis());
537         }
538         return rand;
539     }
540 
541     /**
542      * Returns the SecureRandom used to generate secure random data.
543      * <p>
544      * Creates and initializes if null.
545      * </p>
546      * 
547      * @return the SecureRandom used to generate secure random data
548      */
549     private SecureRandom getSecRan() {
550         if (secRand == null) {
551             secRand = new SecureRandom();
552             secRand.setSeed(System.currentTimeMillis());
553         }
554         return secRand;
555     }
556 
557     /**
558      * Reseeds the random number generator with the supplied seed.
559      * <p>
560      * Will create and initialize if null.
561      * </p>
562      * 
563      * @param seed
564      *            the seed value to use
565      */
566     public void reSeed(long seed) {
567         if (rand == null) {
568             rand = new JDKRandomGenerator();
569         }
570         rand.setSeed(seed);
571     }
572 
573     /**
574      * Reseeds the secure random number generator with the current time in
575      * milliseconds.
576      * <p>
577      * Will create and initialize if null.
578      * </p>
579      */
580     public void reSeedSecure() {
581         if (secRand == null) {
582             secRand = new SecureRandom();
583         }
584         secRand.setSeed(System.currentTimeMillis());
585     }
586 
587     /**
588      * Reseeds the secure random number generator with the supplied seed.
589      * <p>
590      * Will create and initialize if null.
591      * </p>
592      * 
593      * @param seed
594      *            the seed value to use
595      */
596     public void reSeedSecure(long seed) {
597         if (secRand == null) {
598             secRand = new SecureRandom();
599         }
600         secRand.setSeed(seed);
601     }
602 
603     /**
604      * Reseeds the random number generator with the current time in
605      * milliseconds.
606      */
607     public void reSeed() {
608         if (rand == null) {
609             rand = new JDKRandomGenerator();
610         }
611         rand.setSeed(System.currentTimeMillis());
612     }
613 
614     /**
615      * Sets the PRNG algorithm for the underlying SecureRandom instance using
616      * the Security Provider API. The Security Provider API is defined in <a
617      * href =
618      * "http://java.sun.com/j2se/1.3/docs/guide/security/CryptoSpec.html#AppA">
619      * Java Cryptography Architecture API Specification & Reference.</a>
620      * <p>
621      * <strong>USAGE NOTE:</strong> This method carries <i>significant</i>
622      * overhead and may take several seconds to execute.
623      * </p>
624      * 
625      * @param algorithm
626      *            the name of the PRNG algorithm
627      * @param provider
628      *            the name of the provider
629      * @throws NoSuchAlgorithmException
630      *             if the specified algorithm is not available
631      * @throws NoSuchProviderException
632      *             if the specified provider is not installed
633      */
634     public void setSecureAlgorithm(String algorithm, String provider)
635             throws NoSuchAlgorithmException, NoSuchProviderException {
636         secRand = SecureRandom.getInstance(algorithm, provider);
637     }
638 
639     /**
640      * Generates an integer array of length <code>k</code> whose entries are
641      * selected randomly, without repetition, from the integers
642      * <code>0 through n-1</code> (inclusive).
643      * <p>
644      * Generated arrays represent permutations of <code>n</code> taken
645      * <code>k</code> at a time.
646      * </p>
647      * <p>
648      * <strong>Preconditions:</strong>
649      * <ul>
650      * <li> <code>k <= n</code></li>
651      * <li> <code>n > 0</code></li>
652      * </ul>
653      * If the preconditions are not met, an IllegalArgumentException is thrown.
654      * </p>
655      * <p>
656      * Uses a 2-cycle permutation shuffle. The shuffling process is described <a
657      * href="http://www.maths.abdn.ac.uk/~igc/tch/mx4002/notes/node83.html">
658      * here</a>.
659      * </p>
660      * 
661      * @param n
662      *            domain of the permutation (must be positive)
663      * @param k
664      *            size of the permutation (must satisfy 0 < k <= n).
665      * @return the random permutation as an int array
666      */
667     public int[] nextPermutation(int n, int k) {
668         if (k > n) {
669             throw MathRuntimeException.createIllegalArgumentException(
670                   "permutation k ({0}) exceeds n ({1})", k, n);
671         }
672         if (k == 0) {
673             throw MathRuntimeException.createIllegalArgumentException(
674                   "permutation k ({0}) must be positive", k);
675         }
676 
677         int[] index = getNatural(n);
678         shuffle(index, n - k);
679         int[] result = new int[k];
680         for (int i = 0; i < k; i++) {
681             result[i] = index[n - i - 1];
682         }
683 
684         return result;
685     }
686 
687     /**
688      * Uses a 2-cycle permutation shuffle to generate a random permutation.
689      * <strong>Algorithm Description</strong>: Uses a 2-cycle permutation
690      * shuffle to generate a random permutation of <code>c.size()</code> and
691      * then returns the elements whose indexes correspond to the elements of the
692      * generated permutation. This technique is described, and proven to
693      * generate random samples, <a
694      * href="http://www.maths.abdn.ac.uk/~igc/tch/mx4002/notes/node83.html">
695      * here</a>
696      * 
697      * @param c
698      *            Collection to sample from.
699      * @param k
700      *            sample size.
701      * @return the random sample.
702      */
703     public Object[] nextSample(Collection<?> c, int k) {
704         int len = c.size();
705         if (k > len) {
706             throw MathRuntimeException.createIllegalArgumentException(
707                   "sample size ({0}) exceeds collection size ({1})");
708         }
709         if (k <= 0) {
710             throw MathRuntimeException.createIllegalArgumentException(
711                   "sample size must be positive ({0})", k);
712         }
713 
714         Object[] objects = c.toArray();
715         int[] index = nextPermutation(len, k);
716         Object[] result = new Object[k];
717         for (int i = 0; i < k; i++) {
718             result[i] = objects[index[i]];
719         }
720         return result;
721     }
722 
723     // ------------------------Private methods----------------------------------
724 
725     /**
726      * Uses a 2-cycle permutation shuffle to randomly re-order the last elements
727      * of list.
728      * 
729      * @param list
730      *            list to be shuffled
731      * @param end
732      *            element past which shuffling begins
733      */
734     private void shuffle(int[] list, int end) {
735         int target = 0;
736         for (int i = list.length - 1; i >= end; i--) {
737             if (i == 0) {
738                 target = 0;
739             } else {
740                 target = nextInt(0, i);
741             }
742             int temp = list[target];
743             list[target] = list[i];
744             list[i] = temp;
745         }
746     }
747 
748     /**
749      * Returns an array representing n.
750      * 
751      * @param n
752      *            the natural number to represent
753      * @return array with entries = elements of n
754      */
755     private int[] getNatural(int n) {
756         int[] natural = new int[n];
757         for (int i = 0; i < n; i++) {
758             natural[i] = i;
759         }
760         return natural;
761     }
762 
763 }