/*
  Fisher-Yates shuffle, or Knuth shuffle

  Referenece:  http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
*/

import java.util.Arrays;
import java.util.Random;

public final class Shuffle {

   private static final Random RNG =
      new Random (Long.getLong ("seed", System.nanoTime()));

   // Randomly permute the elements of the array 'x'
   public static void shuffle (final int[] x) {
      final int n = x.length;
      for (int i=0; i<n-1; i++) {
         // Randomly select a position in the range i..n-1
         final int j = i + RNG.nextInt (n-i);
         // Swap elements at position i and j
         final int t = x[j]; x[j] = x[i]; x[i] = t; 
      } 
   }

   // Randomly permute the elements of the array 'x'
   public static void shuffle2 (final int[] x) {
      for (int i=x.length-1; i>0; i--) {
         // Randomly select a position in the range 0..i
         final int j = RNG.nextInt (i+1);
         // Swap elements at position i and j
         final int t = x[j]; x[j] = x[i]; x[i] = t; 
      } 
   }


   /*
      Sampling without replacement, as in lotteries: "pick six numbers
      from 1 to 42", can now easily be implmented by fairly permuting
      the numbers 1 to 42 and taking the first six.
   */

   public static void main (final String[] args) {
      final int[] intArray  = {3, 2, 1, 9, 4, 5, 6, 8, 7};
      System.out.println (Arrays.toString (intArray));
      shuffle (intArray);
      System.out.println (Arrays.toString (intArray));
   }

}