Sunday, June 16, 2013

Deck Shuffling

How would you shuffle a deck of cards or generally an array of distinct integers? The shuffle should happen in such a way that every possible reordering is equally likely. Of course it sounds like we should use a random number, but how to ensure the equal probability of each reordering?

There's probably multiple solutions, but the one I liked is a solution that takes O(n) time and no additional space. It is the Fisher-Yates shuffle. What we have to do is traverse the array once and swap each element with a random element that doesn't appear before the current index.

The code is very simple and looks like this:

- The random method is a method that generates a random number within the specified range. This is trivial and could look like this:
- The swap method is a method that swaps 2 elements in an array with the specified index, the implementation is also trivial. It may look like this:

No comments:

Post a Comment