Fisher Yates Shuffle

# Fisher Yates Shuffle

July 14, 2016

When generating random samples, Relativity uses an algorithm called the Fisher-Yates shuffle. Â See the documentation of the shuffling process on the kCura website here. Â  The Fisher-Yates shuffle creates a random sequence of items in a closed set by picking a random number, n, Â and then removing the nth occurrence of that number (counting from the end) in the original set and moving it to a new list. Â This process is repeated until all of the numbers in the set have been removed from the original set. Â  Â See this example from the Wikipedia page for the Fisher-Yates algorithm:

Â

Â So after the first selection, we pick a random number N between 1 and 7 (we 'roll' the dice so to speak), 1 to 7 beingÂ the count of the remaining number of items in the set, and then take out the nth occurrence of that number counting from the end of the list. Â

Â

Â

Random sampling can be performed in Excel using the method described in this blog post. Â  Â In this example we put the numbers in our set from 1 to 8 in column A. Â  Then we use this formula:

Â

=RANDBETWEEN(\$A\$2,\$A\$9)

Â

to generate random selections from the set in column B. Â Â But the trouble is that the numbers repeat. Â  Â Proceed by entering the numbers from the set in first row beginning in column C. Â  Then enter this formula in C2:

Â

=IF(C\$1=\$A2,INDEX(IF(\$A2=1,\$C\$1:\$J\$1,\$C1:\$J1),\$B2),IF(C\$1=\$B2,INDEX(IF(\$A2=1,\$C\$1:\$J1,\$C1:\$J1),\$A2),IF(\$A2=1,C\$1,C1)))

Â

. . . then drag it to the right and down. Â  Â The numbers in red at C3:J9 are our random set of numbers. Â  Â

Â

Â

Â

Â

Â

Â