Why is fisher yates the most useful shuffling algorithm?

Question

Would you say modern version of fisher yates is the most unbiased shuffling algorithm? How would you explain that each element in the array has a probability of 1/n being in its original spot?

Answer 1

Given a perfect pseudo-random number generator (the Mersenne Twister is very close), the Fisher-Yates algorithm is perfectly unbiased in that every permutation has an equal probability of occurring. This is easy to prove using induction. The Fisher-Yates algorithm can be written recursively as follows (in Python syntax pseudocode):

def fisherYatesShuffle(array):
    if len(array) < 2:
        return

    firstElementIndex = uniform(0, len(array))
    swap(array[0], array[firstElementIndex])
    fisherYatesShuffle(array[1:])

Each index has an equal probability of being selected as firstElementIndex. When you recurse, you now have an equal probability of choosing any of the elements that are still left.

Edit: The algorithm has been mathematically proven to be unbiased. Since the algorithm is non-deterministic, the best way to test whether an implementation works properly is statistically. I would take an array of some arbitrary but small size, shuffle it a bunch of times (starting with the same permutation as input each time) and count the number of times each output permutation occurs. Then, I'd use Pearson's Chi-square Test to test this distribution for uniformity.