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 }