- 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?
kberg Feb 16th, 2012 153 Never
RAW Paste Data