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: 831510 $ $Date: 2009-10-30 22:30:18 -0400 (Fri, 30 Oct 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            double r = getRan().nextDouble();
187            return (int) ((r * upper) + ((1.0 - r) * lower) + r);
188        }
189    
190        /**
191         * Generate a random long value uniformly distributed between
192         * <code>lower</code> and <code>upper</code>, inclusive.
193         *
194         * @param lower
195         *            the lower bound.
196         * @param upper
197         *            the upper bound.
198         * @return the random integer.
199         */
200        public long nextLong(long lower, long upper) {
201            if (lower >= upper) {
202                throw MathRuntimeException.createIllegalArgumentException(
203                      "upper bound ({0}) must be greater than lower bound ({1})",
204                      upper, lower);
205            }
206            double r = getRan().nextDouble();
207            return (long) ((r * upper) + ((1.0 - r) * lower) + r);
208        }
209    
210        /**
211         * {@inheritDoc}
212         * <p>
213         * <strong>Algorithm Description:</strong> hex strings are generated in
214         * 40-byte segments using a 3-step process.
215         * <ol>
216         * <li>
217         * 20 random bytes are generated using the underlying
218         * <code>SecureRandom</code>.</li>
219         * <li>
220         * SHA-1 hash is applied to yield a 20-byte binary digest.</li>
221         * <li>
222         * Each byte of the binary digest is converted to 2 hex digits.</li>
223         * </ol>
224         * </p>
225         *
226         * @param len
227         *            the length of the generated string
228         * @return the random string
229         */
230        public String nextSecureHexString(int len) {
231            if (len <= 0) {
232                throw MathRuntimeException.createIllegalArgumentException(
233                      "length must be positive ({0})", len);
234            }
235    
236            // Get SecureRandom and setup Digest provider
237            SecureRandom secRan = getSecRan();
238            MessageDigest alg = null;
239            try {
240                alg = MessageDigest.getInstance("SHA-1");
241            } catch (NoSuchAlgorithmException ex) {
242                // this should never happen
243                throw MathRuntimeException.createInternalError(ex);
244            }
245            alg.reset();
246    
247            // Compute number of iterations required (40 bytes each)
248            int numIter = (len / 40) + 1;
249    
250            StringBuffer outBuffer = new StringBuffer();
251            for (int iter = 1; iter < numIter + 1; iter++) {
252                byte[] randomBytes = new byte[40];
253                secRan.nextBytes(randomBytes);
254                alg.update(randomBytes);
255    
256                // Compute hash -- will create 20-byte binary hash
257                byte hash[] = alg.digest();
258    
259                // Loop over the hash, converting each byte to 2 hex digits
260                for (int i = 0; i < hash.length; i++) {
261                    Integer c = Integer.valueOf(hash[i]);
262    
263                    /*
264                     * Add 128 to byte value to make interval 0-255 This guarantees
265                     * <= 2 hex digits from toHexString() toHexString would
266                     * otherwise add 2^32 to negative arguments
267                     */
268                    String hex = Integer.toHexString(c.intValue() + 128);
269    
270                    // Keep strings uniform length -- guarantees 40 bytes
271                    if (hex.length() == 1) {
272                        hex = "0" + hex;
273                    }
274                    outBuffer.append(hex);
275                }
276            }
277            return outBuffer.toString().substring(0, len);
278        }
279    
280        /**
281         * Generate a random int value uniformly distributed between
282         * <code>lower</code> and <code>upper</code>, inclusive. This algorithm uses
283         * a secure random number generator.
284         *
285         * @param lower
286         *            the lower bound.
287         * @param upper
288         *            the upper bound.
289         * @return the random integer.
290         */
291        public int nextSecureInt(int lower, int upper) {
292            if (lower >= upper) {
293                throw MathRuntimeException.createIllegalArgumentException(
294                      "upper bound ({0}) must be greater than lower bound ({1})",
295                      upper, lower);
296            }
297            SecureRandom sec = getSecRan();
298            return lower + (int) (sec.nextDouble() * (upper - lower + 1));
299        }
300    
301        /**
302         * Generate a random long value uniformly distributed between
303         * <code>lower</code> and <code>upper</code>, inclusive. This algorithm uses
304         * a secure random number generator.
305         *
306         * @param lower
307         *            the lower bound.
308         * @param upper
309         *            the upper bound.
310         * @return the random integer.
311         */
312        public long nextSecureLong(long lower, long upper) {
313            if (lower >= upper) {
314                throw MathRuntimeException.createIllegalArgumentException(
315                      "upper bound ({0}) must be greater than lower bound ({1})",
316                      upper, lower);
317            }
318            SecureRandom sec = getSecRan();
319            return lower + (long) (sec.nextDouble() * (upper - lower + 1));
320        }
321    
322        /**
323         * {@inheritDoc}
324         * <p>
325         * <strong>Algorithm Description</strong>:
326         * <ul><li> For small means, uses simulation of a Poisson process
327         * using Uniform deviates, as described
328         * <a href="http://irmi.epfl.ch/cmos/Pmmi/interactive/rng7.htm"> here.</a>
329         * The Poisson process (and hence value returned) is bounded by 1000 * mean.</li>
330         *
331         * <li> For large means, uses the rejection algorithm described in <br/>
332         * Devroye, Luc. (1981).<i>The Computer Generation of Poisson Random Variables</i>
333         * <strong>Computing</strong> vol. 26 pp. 197-207.</li></ul></p>
334         *
335         * @param mean mean of the Poisson distribution.
336         * @return the random Poisson value.
337         */
338        public long nextPoisson(double mean) {
339            if (mean <= 0) {
340                throw MathRuntimeException.createIllegalArgumentException(
341                      "the Poisson mean must be positive ({0})", mean);
342            }
343    
344            final RandomGenerator generator = getRan();
345    
346            final double pivot = 40.0d;
347            if (mean < pivot) {
348                double p = Math.exp(-mean);
349                long n = 0;
350                double r = 1.0d;
351                double rnd = 1.0d;
352    
353                while (n < 1000 * mean) {
354                    rnd = generator.nextDouble();
355                    r = r * rnd;
356                    if (r >= p) {
357                        n++;
358                    } else {
359                        return n;
360                    }
361                }
362                return n;
363            } else {
364                final double lambda = Math.floor(mean);
365                final double lambdaFractional = mean - lambda;
366                final double logLambda = Math.log(lambda);
367                final double logLambdaFactorial = MathUtils.factorialLog((int) lambda);
368                final long y2 = lambdaFractional < Double.MIN_VALUE ? 0 : nextPoisson(lambdaFractional);
369                final double delta = Math.sqrt(lambda * Math.log(32 * lambda / Math.PI + 1));
370                final double halfDelta = delta / 2;
371                final double twolpd = 2 * lambda + delta;
372                final double a1 = Math.sqrt(Math.PI * twolpd) * Math.exp(1 / 8 * lambda);
373                final double a2 = (twolpd / delta) * Math.exp(-delta * (1 + delta) / twolpd);
374                final double aSum = a1 + a2 + 1;
375                final double p1 = a1 / aSum;
376                final double p2 = a2 / aSum;
377                final double c1 = 1 / (8 * lambda);
378    
379                double x = 0;
380                double y = 0;
381                double v = 0;
382                int a = 0;
383                double t = 0;
384                double qr = 0;
385                double qa = 0;
386                for (;;) {
387                    final double u = nextUniform(0.0, 1);
388                    if (u <= p1) {
389                        final double n = nextGaussian(0d, 1d);
390                        x = n * Math.sqrt(lambda + halfDelta) - 0.5d;
391                        if (x > delta || x < -lambda) {
392                            continue;
393                        }
394                        y = x < 0 ? Math.floor(x) : Math.ceil(x);
395                        final double e = nextExponential(1d);
396                        v = -e - (n * n / 2) + c1;
397                    } else {
398                        if (u > p1 + p2) {
399                            y = lambda;
400                            break;
401                        } else {
402                            x = delta + (twolpd / delta) * nextExponential(1d);
403                            y = Math.ceil(x);
404                            v = -nextExponential(1d) - delta * (x + 1) / twolpd;
405                        }
406                    }
407                    a = x < 0 ? 1 : 0;
408                    t = y * (y + 1) / (2 * lambda);
409                    if (v < -t && a == 0) {
410                        y = lambda + y;
411                        break;
412                    }
413                    qr = t * ((2 * y + 1) / (6 * lambda) - 1);
414                    qa = qr - (t * t) / (3 * (lambda + a * (y + 1)));
415                    if (v < qa) {
416                        y = lambda + y;
417                        break;
418                    }
419                    if (v > qr) {
420                        continue;
421                    }
422                    if (v < y * logLambda - MathUtils.factorialLog((int) (y + lambda)) + logLambdaFactorial) {
423                        y = lambda + y;
424                        break;
425                    }
426                }
427                return y2 + (long) y;
428            }
429        }
430    
431        /**
432         * Generate a random value from a Normal (a.k.a. Gaussian) distribution with
433         * the given mean, <code>mu</code> and the given standard deviation,
434         * <code>sigma</code>.
435         *
436         * @param mu
437         *            the mean of the distribution
438         * @param sigma
439         *            the standard deviation of the distribution
440         * @return the random Normal value
441         */
442        public double nextGaussian(double mu, double sigma) {
443            if (sigma <= 0) {
444                throw MathRuntimeException.createIllegalArgumentException(
445                      "standard deviation must be positive ({0})", sigma);
446            }
447            return sigma * getRan().nextGaussian() + mu;
448        }
449    
450        /**
451         * Returns a random value from an Exponential distribution with the given
452         * mean.
453         * <p>
454         * <strong>Algorithm Description</strong>: Uses the <a
455         * href="http://www.jesus.ox.ac.uk/~clifford/a5/chap1/node5.html"> Inversion
456         * Method</a> to generate exponentially distributed random values from
457         * uniform deviates.
458         * </p>
459         *
460         * @param mean the mean of the distribution
461         * @return the random Exponential value
462         */
463        public double nextExponential(double mean) {
464            if (mean <= 0.0) {
465                throw MathRuntimeException.createIllegalArgumentException(
466                      "mean must be positive ({0})", mean);
467            }
468            final RandomGenerator generator = getRan();
469            double unif = generator.nextDouble();
470            while (unif == 0.0d) {
471                unif = generator.nextDouble();
472            }
473            return -mean * Math.log(unif);
474        }
475    
476        /**
477         * {@inheritDoc}
478         * <p>
479         * <strong>Algorithm Description</strong>: scales the output of
480         * Random.nextDouble(), but rejects 0 values (i.e., will generate another
481         * random double if Random.nextDouble() returns 0). This is necessary to
482         * provide a symmetric output interval (both endpoints excluded).
483         * </p>
484         *
485         * @param lower
486         *            the lower bound.
487         * @param upper
488         *            the upper bound.
489         * @return a uniformly distributed random value from the interval (lower,
490         *         upper)
491         */
492        public double nextUniform(double lower, double upper) {
493            if (lower >= upper) {
494                throw MathRuntimeException.createIllegalArgumentException(
495                      "upper bound ({0}) must be greater than lower bound ({1})",
496                      upper, lower);
497            }
498            final RandomGenerator generator = getRan();
499    
500            // ensure nextDouble() isn't 0.0
501            double u = generator.nextDouble();
502            while (u <= 0.0) {
503                u = generator.nextDouble();
504            }
505    
506            return lower + u * (upper - lower);
507        }
508    
509        /**
510         * Returns the RandomGenerator used to generate non-secure random data.
511         * <p>
512         * Creates and initializes a default generator if null.
513         * </p>
514         *
515         * @return the Random used to generate random data
516         * @since 1.1
517         */
518        private RandomGenerator getRan() {
519            if (rand == null) {
520                rand = new JDKRandomGenerator();
521                rand.setSeed(System.currentTimeMillis());
522            }
523            return rand;
524        }
525    
526        /**
527         * Returns the SecureRandom used to generate secure random data.
528         * <p>
529         * Creates and initializes if null.
530         * </p>
531         *
532         * @return the SecureRandom used to generate secure random data
533         */
534        private SecureRandom getSecRan() {
535            if (secRand == null) {
536                secRand = new SecureRandom();
537                secRand.setSeed(System.currentTimeMillis());
538            }
539            return secRand;
540        }
541    
542        /**
543         * Reseeds the random number generator with the supplied seed.
544         * <p>
545         * Will create and initialize if null.
546         * </p>
547         *
548         * @param seed
549         *            the seed value to use
550         */
551        public void reSeed(long seed) {
552            if (rand == null) {
553                rand = new JDKRandomGenerator();
554            }
555            rand.setSeed(seed);
556        }
557    
558        /**
559         * Reseeds the secure random number generator with the current time in
560         * milliseconds.
561         * <p>
562         * Will create and initialize if null.
563         * </p>
564         */
565        public void reSeedSecure() {
566            if (secRand == null) {
567                secRand = new SecureRandom();
568            }
569            secRand.setSeed(System.currentTimeMillis());
570        }
571    
572        /**
573         * Reseeds the secure random number generator with the supplied seed.
574         * <p>
575         * Will create and initialize if null.
576         * </p>
577         *
578         * @param seed
579         *            the seed value to use
580         */
581        public void reSeedSecure(long seed) {
582            if (secRand == null) {
583                secRand = new SecureRandom();
584            }
585            secRand.setSeed(seed);
586        }
587    
588        /**
589         * Reseeds the random number generator with the current time in
590         * milliseconds.
591         */
592        public void reSeed() {
593            if (rand == null) {
594                rand = new JDKRandomGenerator();
595            }
596            rand.setSeed(System.currentTimeMillis());
597        }
598    
599        /**
600         * Sets the PRNG algorithm for the underlying SecureRandom instance using
601         * the Security Provider API. The Security Provider API is defined in <a
602         * href =
603         * "http://java.sun.com/j2se/1.3/docs/guide/security/CryptoSpec.html#AppA">
604         * Java Cryptography Architecture API Specification & Reference.</a>
605         * <p>
606         * <strong>USAGE NOTE:</strong> This method carries <i>significant</i>
607         * overhead and may take several seconds to execute.
608         * </p>
609         *
610         * @param algorithm
611         *            the name of the PRNG algorithm
612         * @param provider
613         *            the name of the provider
614         * @throws NoSuchAlgorithmException
615         *             if the specified algorithm is not available
616         * @throws NoSuchProviderException
617         *             if the specified provider is not installed
618         */
619        public void setSecureAlgorithm(String algorithm, String provider)
620                throws NoSuchAlgorithmException, NoSuchProviderException {
621            secRand = SecureRandom.getInstance(algorithm, provider);
622        }
623    
624        /**
625         * Generates an integer array of length <code>k</code> whose entries are
626         * selected randomly, without repetition, from the integers
627         * <code>0 through n-1</code> (inclusive).
628         * <p>
629         * Generated arrays represent permutations of <code>n</code> taken
630         * <code>k</code> at a time.
631         * </p>
632         * <p>
633         * <strong>Preconditions:</strong>
634         * <ul>
635         * <li> <code>k <= n</code></li>
636         * <li> <code>n > 0</code></li>
637         * </ul>
638         * If the preconditions are not met, an IllegalArgumentException is thrown.
639         * </p>
640         * <p>
641         * Uses a 2-cycle permutation shuffle. The shuffling process is described <a
642         * href="http://www.maths.abdn.ac.uk/~igc/tch/mx4002/notes/node83.html">
643         * here</a>.
644         * </p>
645         *
646         * @param n
647         *            domain of the permutation (must be positive)
648         * @param k
649         *            size of the permutation (must satisfy 0 < k <= n).
650         * @return the random permutation as an int array
651         */
652        public int[] nextPermutation(int n, int k) {
653            if (k > n) {
654                throw MathRuntimeException.createIllegalArgumentException(
655                      "permutation k ({0}) exceeds n ({1})", k, n);
656            }
657            if (k == 0) {
658                throw MathRuntimeException.createIllegalArgumentException(
659                      "permutation k ({0}) must be positive", k);
660            }
661    
662            int[] index = getNatural(n);
663            shuffle(index, n - k);
664            int[] result = new int[k];
665            for (int i = 0; i < k; i++) {
666                result[i] = index[n - i - 1];
667            }
668    
669            return result;
670        }
671    
672        /**
673         * Uses a 2-cycle permutation shuffle to generate a random permutation.
674         * <strong>Algorithm Description</strong>: Uses a 2-cycle permutation
675         * shuffle to generate a random permutation of <code>c.size()</code> and
676         * then returns the elements whose indexes correspond to the elements of the
677         * generated permutation. This technique is described, and proven to
678         * generate random samples, <a
679         * href="http://www.maths.abdn.ac.uk/~igc/tch/mx4002/notes/node83.html">
680         * here</a>
681         *
682         * @param c
683         *            Collection to sample from.
684         * @param k
685         *            sample size.
686         * @return the random sample.
687         */
688        public Object[] nextSample(Collection<?> c, int k) {
689            int len = c.size();
690            if (k > len) {
691                throw MathRuntimeException.createIllegalArgumentException(
692                      "sample size ({0}) exceeds collection size ({1})");
693            }
694            if (k <= 0) {
695                throw MathRuntimeException.createIllegalArgumentException(
696                      "sample size must be positive ({0})", k);
697            }
698    
699            Object[] objects = c.toArray();
700            int[] index = nextPermutation(len, k);
701            Object[] result = new Object[k];
702            for (int i = 0; i < k; i++) {
703                result[i] = objects[index[i]];
704            }
705            return result;
706        }
707    
708        // ------------------------Private methods----------------------------------
709    
710        /**
711         * Uses a 2-cycle permutation shuffle to randomly re-order the last elements
712         * of list.
713         *
714         * @param list
715         *            list to be shuffled
716         * @param end
717         *            element past which shuffling begins
718         */
719        private void shuffle(int[] list, int end) {
720            int target = 0;
721            for (int i = list.length - 1; i >= end; i--) {
722                if (i == 0) {
723                    target = 0;
724                } else {
725                    target = nextInt(0, i);
726                }
727                int temp = list[target];
728                list[target] = list[i];
729                list[i] = temp;
730            }
731        }
732    
733        /**
734         * Returns an array representing n.
735         *
736         * @param n
737         *            the natural number to represent
738         * @return array with entries = elements of n
739         */
740        private int[] getNatural(int n) {
741            int[] natural = new int[n];
742            for (int i = 0; i < n; i++) {
743                natural[i] = i;
744            }
745            return natural;
746        }
747    
748    }