## Saturday, October 18, 2014

### Fisher–Yates shuffle Java Implementation

The Fisher–Yates shuffle (named after Ronald Fisher and Frank Yates), also known as the Knuth shuffle (after Donald Knuth), is an algorithm for generating a random permutation of a finite set—in plain terms, for randomly shuffling the set.

Algorithm:
1. Iterate from Index 0 to N,
2. For index i between 0 to N, select a random number between 0 and i (inclusive) and swap the numbers at the two positions.
3. After index N has been processed, the array is shuffled.

Source:

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

public class KnuthShuffle {

public static <T> void swap(T[] array, int i, int j){
T temp = array[i];
array[i] = array[j];
array[j] = temp;
}

public static <T> T[] shuffle(T[] array){
Random rand = new Random();

for(int i = 0;i<array.length; ++i){
swap(array, rand.nextInt(i+1), i);
//System.out.println(Arrays.toString(array));
}
return array;
}
public static void main(String[] args){
Integer[] array = new Integer[]{1, 2, 3, 4, 5, 6, 7};
System.out.println(Arrays.toString(shuffle(array)));
}
}```
` `
Output:
[5, 6, 1, 7, 2, 3, 4]