The Fisher-Yates algorithm is a simple list shuffling algorithm that is unbiased. The algorithm runs in O(n) and uses O(1) space. Because of Scratch limitations, this one runs in O(n) and O(n) space because of the temporary list. The steps for this algorithm are: 1. Start with the base list 2. Let i be the last element of the list. 3. Pick a random number between 1 and i. 4. Swap the two elements. 5. decrease i by 1. 6. Repeat steps 3 - 5 until i is 1. In pseudocode: FUNCTION fisherYatesShuffle(arr) RETURNS array FOR i = #arr, 1, -1 DO j = RANDOM(1, i) SWAP arr[i], arr[j] return arr END FUNCTION
Proof: For every P(n), the algorithm is unbiased. If the algorithm is unbiased, then each possible permutation of the list has a 1/n! chance of happening. P(1) is trivially true because a list of one element has a 100% chance of being in the list. Therefore, the algorithm has a 1/(1)! chance of producing 1 permutation. To prove the algorithm by induction, then for some arbitrary n, n+1 must also be true. P(n+1) produces a list of n+1 elements. The algorithm picks from 1 - n+1 (this number will be denoted as j) and assigns it to the list, meaning each permutation of the sublist from 1 - j has a chance of: 1/n * 1/(n-1) * 1/(n-2) * ... 1/1 This is equivalent to 1/(n!) because a factorial is defined as n * (n-1) * (n-2) * ... 1. Therefore, the algorithm is unbiased and can produce any permutation of the list with an equally likely chance. Fun Fact: Factorials grow extremely large. So large in fact that 10! is already 3628800. A standard deck of cards has 52! permutations, which is around 8.07 * 10^67! That's larger than all conceivable atoms in the universe!
