Lesson 3

How to implement a method that takes a sequence as input and shuffles it randomly so that the resulting distribution is uniform?

We can enumerate all permutations of a set (e.g., \([n]\)) by traversing such a tree.

This tree suggests a general method: the first position may (with equal probability) contain any element, the second position may contain any of the remaining elements, and so on. The Fisher–Yates shuffle (also known as Knuth shuffle) algorithm implements exactly this idea (and additionally ensures that shuffling is done in-place within the given sequence): on the \(i\)-th iteration, we swap the \(i\)-th element with a randomly chosen element that is not to its left. Below is an implementation of this algorithm, which traverses the array from right to left. The \(\texttt{random.shuffle()}\) method is implemented in the same way.

from random import random, seed


def shuffle(lst):
    for i in reversed(range(1, len(lst))):
        j = int(random() * (i + 1))
        lst[i], lst[j] = lst[j], lst[i]


seed(17)
lst = list(range(10))
shuffle(lst)
print(lst)

[1, 9, 0, 6, 3, 4, 2, 8, 7, 5]