Today, I had a chance to use Fisher Yates algorithm. Fisher Yates algorithm shuffles the items in a list.

Here is the problem statement:

Out of an array of N items, randomly pick K items where 0 < K < N.

My first naive solution of the problem was as follows:

Pick an index at random. Add it to a set. Keep doing it till there are k items in the set.

The code has a problem. To pick all the items in a random order, it takes a long time for the loop to terminate.

After a bit of search, I landed up in Fisher Yates shuffle algorithm. Shuffle algorithm works similar. Move back from the last item in the array. Pick a random index. Shuffle the items in the random index and the current index. Keep repeating till all items in the array are shuffled. A variation of Fisher Yates shuffle algorithm is the random select solution. In random select, we shuffle K times where K < N. In that way, we terminate the loop earlier. Also, there is no problem with long loops we witnessed in the earlier solution.

The algorithm runs in O(n) when K is nearly equivalent to N. But, it runs much faster as O(1) when K is much smaller than N.

Random Select or Shuffle using Fisher Yates algorithm
Tagged on: