Fisher-Yates Shuffle: A Visual Proof
What do we mean by a random shuffle? We mean uniformly random - that each element in the list could be shuffled into each position with equal probability.
How frequently should the element ei be shuffled into the position j? 1 in n times. Or position k? Also 1 in n times. Each element in each position 1 out of n times.
The fisher-yates algorithm shuffles a list with the following steps:
- swap the last element, en, with the element ei at a random position i.
- repeat/recurse step 1 on the sublist from e0 to en-1.
- stop when the list you are shuffling only has a single element or less.
in python the code looks like:
a = [ ... ] for i in range(len(a) - 1, 0, -1): # n-1, n-2, n-3, ... 1 j = random.randint(0, i) a[i], a[j] = a[j], a[i]
Simple, no? The animation of an example shuffle is also pretty simple. We start with the last element, swap (possibly into the same position), then fix the last element in position and move on to the next position for swapping.
In the visualization above, we were only demonstrating one possible shuffle each time. What if we considered all possible swaps at each iteration and kept track of the probability each element was in each position? If a shuffle was truly random then each element, represented by color, should result in each position equally after shuffling the whole list.
In the visualization below, we highlight two positions before considering the swap. Colors represent elements. Each row represents the result of an iteration. A multicolored square means for that specific position we had a certain probability of being those elements, proportional to area of the color. After an iteration we stop considering the last element, hence the diagonal shape. After each iteration you can sort of see that the last position has equal chance to be any element. Once we are done iterating we simplify the visual probabilities in each position and collapse the diagonal. You can easily see that algorithm results in each element possibly being moved to each position with uniform probability.