Some time this past year, while I was walking down the street with some friends in Boston, a peculiar response to my appearance was uttered loudly, and almost angrily, by a man proceeding down the sidewalk in a wheelchair in the opposite direction: “Goddamnit, that’s the fourth redhead I’ve seen today!”
It is with similar bewildered vigor that I now can utter, “Goddamnit, that’s the second time I’ve used the Fisher-Yates Shuffle today…” So I thought I’d blog about it because it’s a neat little algorithm (no, it’s not an obscure dance move from the ’20s despite its misleading name) and I am particularly excited about the second application where I used it, because I believe it resulted in a clever solution to the problem at hand (namely creating a randomized “bitmap” of sorts to layer on top of an ordered list of values to control which values in that list should be blanked out).
The algorithm, which runs with O(n) complexity (which fwiw is quite good as algorithm complexities go), is as follows (the excerpt below is in C):
In short, what the algorithm does is start at index 0 of an array of to-be-randomized values, and pick a random index from the array from 0 to (array length - 1) whose value to swap with the 0th value. Once this is done, proceed to index 1 and choose another random index whose value to swap with index 1’s value, chosen from index 1 to (length - 1), etc…
One operation for each of n iterations of application where n is the number of items in the array, hence O(n). Simple, elegant and cool!