14/02/2018

[Java] Fisher-Yates array shuffle

The Fisher–Yates shuffle is an algorithm for generating a random permutation of a finite sequence. It can be coded to run in-place and in O(N) time where N is the input array size.

The idea is quite simple yet effective: while scanning the array from the end, select a random index with which to swap that element for among an always shrinking set of possibilities. Namely, use a getRandom function that accepts a floor and a ceiling as input and reduce the ceiling by 1 at each iteration, until the whole array has been processed.

You can check my implementation of FisherYatesShuffle on my Gist alongside some test cases in FisherYatesJTests.

Note: since we are supposed to generate truly random permutations of the input array, we have no simple way of checking for errors except to verify the output distribution itself to determine whether a bias exists or not. Therefore the current test could be extended to record for all the algorithm iterations the result of the shuffle and compare the results at the end among themselves.

No comments:

Post a Comment

With great power comes great responsibility.

Da grandi poteri derivano grandi responsabilità.