- The algorithm iterates n times. Each iteration, m, selects a random index from 0-m-1, pulls it from the source array, and pushes it to the destination array. The array is now size m-1. When the array size is 1, the random number generator selects a value from 0-0.
- So, when m=1, it selects one possible value
- m=2, selects one of two possible values.
- m=3, selects one of three possible values.
- m=n, selects one of n values.
- Now I wave my hands a little to demonstrate my lack of past math skills, and presto! the use of the randomizer results in one of n! possible outcomes. How's that?
RAW Paste Data