Python – How Python random shuffle works

pythonrandom

How shuffle from random works in Python?

I ask because it works very fast. When I try to write shuffle it works 1 minute for 10^6 element, but Python shuffle does that in 8 sec?

Best Answer

Python's random.shuffle uses the Fisher-Yates shuffle, which runs in O(n) time and is proven to be a perfect shuffle (assuming a good random number generator).

It iterates the array from the last to the first entry, switching each entry with an entry at a random index below it.

The basic process of Fisher–Yates shuffling is similar to randomly picking numbered tickets out of a hat, or cards from a deck, one after another until there are no more left. What the specific algorithm provides is a way of doing this numerically in an efficient and rigorous manner that, properly done, guarantees an unbiased result...

The modern... solution is to move the "struck" numbers to the end of the list by swapping them with the last unstruck number at each iteration. This reduces the algorithm's time complexity to O(n), compared to O(n2) for the naive implementation. This change gives the following algorithm (for a zero-based array).

To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]
Related Topic