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 tex_85d18d8fee621fa7e40e8f59d6677e7d Teaching Kids Programming - The Fisher–Yates Random Shuffle Algorithm in Python algorithms python teaching kids programming youtube video permutation – so if we do a shuffling, each permutation needs to be in theory tex_8d6b565c4b70076707839a6c4d93be23 Teaching Kids Programming - The Fisher–Yates Random Shuffle Algorithm in Python algorithms python teaching kids programming youtube video 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

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
a WordPress rating system
457 words
Last Post: Teaching Kids Programming - Image Flood Fill via DFS and BFS Algorithm
Next Post: Teaching Kids Programming - Run-Length Decoding/Decompression Algorithm

The Permanent URL is: Teaching Kids Programming – The Fisher–Yates Random Shuffle Algorithm in Python

Leave a Reply