001    /*
002     * Licensed to the Apache Software Foundation (ASF) under one or more
003     * contributor license agreements.  See the NOTICE file distributed with
004     * this work for additional information regarding copyright ownership.
005     * The ASF licenses this file to You under the Apache License, Version 2.0
006     * (the "License"); you may not use this file except in compliance with
007     * the License.  You may obtain a copy of the License at
008     *
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     *
011     * Unless required by applicable law or agreed to in writing, software
012     * distributed under the License is distributed on an "AS IS" BASIS,
013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     * See the License for the specific language governing permissions and
015     * limitations under the License.
016     */
017    
018    package org.apache.commons.math.random;
019    
020    import java.io.Serializable;
021    import java.security.MessageDigest;
022    import java.security.SecureRandom;
023    import java.security.NoSuchAlgorithmException;
024    import java.security.NoSuchProviderException;
025    import java.util.Collection;
026    
027    import org.apache.commons.math.MathRuntimeException;
028    import org.apache.commons.math.util.MathUtils;
029    
030    /**
031     * Implements the {@link RandomData} interface using a {@link RandomGenerator}
032     * instance to generate non-secure data and a {@link java.security.SecureRandom}
033     * instance to provide data for the <code>nextSecureXxx</code> methods. If no
034     * <code>RandomGenerator</code> is provided in the constructor, the default is
035     * to use a generator based on {@link java.util.Random}. To plug in a different
036     * implementation, either implement <code>RandomGenerator</code> directly or
037     * extend {@link AbstractRandomGenerator}.
038     * <p>
039     * Supports reseeding the underlying pseudo-random number generator (PRNG). The
040     * <code>SecurityProvider</code> and <code>Algorithm</code> used by the
041     * <code>SecureRandom</code> instance can also be reset.
042     * </p>
043     * <p>
044     * For details on the default PRNGs, see {@link java.util.Random} and
045     * {@link java.security.SecureRandom}.
046     * </p>
047     * <p>
048     * <strong>Usage Notes</strong>:
049     * <ul>
050     * <li>
051     * Instance variables are used to maintain <code>RandomGenerator</code> and
052     * <code>SecureRandom</code> instances used in data generation. Therefore, to
053     * generate a random sequence of values or strings, you should use just
054     * <strong>one</strong> <code>RandomDataImpl</code> instance repeatedly.</li>
055     * <li>
056     * The "secure" methods are *much* slower. These should be used only when a
057     * cryptographically secure random sequence is required. A secure random
058     * sequence is a sequence of pseudo-random values which, in addition to being
059     * well-dispersed (so no subsequence of values is an any more likely than other
060     * subsequence of the the same length), also has the additional property that
061     * knowledge of values generated up to any point in the sequence does not make
062     * it any easier to predict subsequent values.</li>
063     * <li>
064     * When a new <code>RandomDataImpl</code> is created, the underlying random
065     * number generators are <strong>not</strong> intialized. If you do not
066     * explicitly seed the default non-secure generator, it is seeded with the
067     * current time in milliseconds on first use. The same holds for the secure
068     * generator. If you provide a <code>RandomGenerator</code> to the constructor,
069     * however, this generator is not reseeded by the constructor nor is it reseeded
070     * on first use.</li>
071     * <li>
072     * The <code>reSeed</code> and <code>reSeedSecure</code> methods delegate to the
073     * corresponding methods on the underlying <code>RandomGenerator</code> and
074     * <code>SecureRandom</code> instances. Therefore, <code>reSeed(long)</code>
075     * fully resets the initial state of the non-secure random number generator (so
076     * that reseeding with a specific value always results in the same subsequent
077     * random sequence); whereas reSeedSecure(long) does <strong>not</strong>
078     * reinitialize the secure random number generator (so secure sequences started
079     * with calls to reseedSecure(long) won't be identical).</li>
080     * <li>
081     * This implementation is not synchronized.
082     * </ul>
083     * </p>
084     * 
085     * @version $Revision: 772119 $ $Date: 2009-05-06 05:43:28 -0400 (Wed, 06 May 2009) $
086     */
087    public class RandomDataImpl implements RandomData, Serializable {
088    
089        /** Serializable version identifier */
090        private static final long serialVersionUID = -626730818244969716L;
091    
092        /** underlying random number generator */
093        private RandomGenerator rand = null;
094    
095        /** underlying secure random number generator */
096        private SecureRandom secRand = null;
097    
098        /**
099         * 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    }