Search code examples
pythonfisher-yates-shuffle

What is the principle of randomly selecting positions to swap in the shuffle function


Fisher–Yates shuffle means that we take the last number from the selected segment every time and swap it with the previously randomly selected number, iterate continuously, and finally achieve random shuffling.The code for the official Shuffle in python3.6 is as follows

     _int = int
     for i in reversed(range(1, len(x))):
          # pick an element in x[:i+1] with which to exchange x[i]
          j = _int(random() * (i+1))
          x[i], x[j] = x[j], x[i]

Why not just pick the global locations and swap?


Solution

  • random() is a float in the range [0, 1). When you multiply that by i+1, you get a float in the range [0, i+1). When you convert that to an integer, you get an integer in the range [0, i].

    Of course, you could just use random.randint(0, i). And reverse(range(1, len(x)) can be simplified to range(len(x)-1, 0, -1).