Teaching Kids Programming – The Fisher–Yates Random Shuffle Algorithm in Python

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given N items, we know there are total permutation – so if we do a shuffling, each permutation needs to be in theory probability.

If we swap two elements N times, then each element need to be swapped exactly once otherwise the random shuffling is biased. The Fisher-Yates algorithm gives a unbiased shuffling sequence.

Fisher-Yates Random Shuffling Algorithm in Python

The idea is that when an element is swapped out, we don’t swap it again – we can partition the array into two halves, ones that have been swapped and ones that are to swap in next rounds.

1
2
3
4
5

def shuffle(arr):
    for i in range(len(arr)):
        swap_idx = random.randrange(i, len(arr))
        arr[i], arr[swap_idx] = arr[swap_idx], arr[i]
    return self.array

def shuffle(arr):
    for i in range(len(arr)):
        swap_idx = random.randrange(i, len(arr))
        arr[i], arr[swap_idx] = arr[swap_idx], arr[i]
    return self.array

When i reaches the last element, it can only be swapped with itself, and thus we can also loop till len(n)-2 rather than len(n)-1

The time complexity is O(N) and the space complexity of the Fisher-Yates is O(1) constant.

Random Shuffling Algorithms

• The Fisher–Yates Random Shuffle Algorithm
• GoLang: Shuffle the Array
• Teaching Kids Programming – The Fisher–Yates Random Shuffle Algorithm in Python

–EOF (The Ultimate Computing & Technology Blog) —