Arpith Siromoney 💬

Fisher-Yates Shuffle Algorithm

In particular, the most common naive algorithm that comes up is [1]:
naive_shuffle(arr):
  if len(arr) > 1:
    for i in 0 .. len(arr) - 1:
      s = random from inclusive range [0:len(arr)-1]
      swap arr[s] with arr[i]
This algorithm produces results that are badly skewed. For more information consult <a href=http://www.codinghorror.com/blog/2007/12/the-danger-of-naivete.html>this post by Jeff Attwood</a>, and <a href=http://stackoverflow.com/questions/859253/why-does-this-simple-shuffle-algorithm-produce-biased-results-what-is-a-simple%20%282nd%20answer%29>this SO discussion</a>. The correct answer is to use the Fisher-Yates shuffle algorithm:
fisher_yates_shuffle(arr):
  if len(arr) > 1:
    i = len(arr) - 1
    while i > 0:
      s = random from inclusive range [0:i]
      swap arr[s] with arr[i]
      i--

Rewritten,

non_naive_shuffle(arr):
  if len(arr) > 1:
    for i in 0 .. len(arr) - 1:
      s = random from inclusive range [i:len(arr)-1]
      swap arr[s] with arr[i]