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]

No comments:

Post a Comment