Unbiased Randomization with the Fisher-Yates Shuffle
spin.atomicobject.com
Unbiased Randomization with the Fisher-Yates Shuffle
1–10 of 14 posts
Re: Unbiased Randomization with the Fisher-Yates Shuffle
#2If you are using Python, you should use the standard 'random.shuffle' which does use the Fisher-Yates algorithm.
Re: Unbiased Randomization with the Fisher-Yates Shuffle
#3If you are using Python, you should use the standard 'random.shuffle' which does use the Fisher-Yates algorithm.
There's value in knowing how it's implemented.
Re: Unbiased Randomization with the Fisher-Yates Shuffle
#4If you are using Python, you should use the standard 'random.shuffle' which does use the Fisher-Yates algorithm.
There's value in knowing how it's implemented.
Further, there is value in knowing what makes the incorrect ways incorrect. :)
Also, even in the article it noted to use a library if your language allows.
Re: Unbiased Randomization with the Fisher-Yates Shuffle
#5If you are using Python, you should use the standard 'random.shuffle' which does use the Fisher-Yates algorithm.
It does seem strange to say "However, there are plenty of languages that don’t provide built in support for such a function, leaving you on your own." and then show examples in Python.
Re: Unbiased Randomization with the Fisher-Yates Shuffle
#6[deleted]
Re: Unbiased Randomization with the Fisher-Yates Shuffle
#7If you are using Python, you should use the standard 'random.shuffle' which does use the Fisher-Yates algorithm.
If you are using Excel, you might find my blog entry useful: http://kiyototamura.tumblr.com/post/91613880102/generating-a...
Re: Unbiased Randomization with the Fisher-Yates Shuffle
#8[deleted]
The algorithms are different. OP's Fisher-Yates is correct, the only mistake is the last superfluous iteration.
Re: Unbiased Randomization with the Fisher-Yates Shuffle
#9[deleted]
The difference is one character: the index of the element to swap.
It's subtle.
Re: Unbiased Randomization with the Fisher-Yates Shuffle
#10On second read, I realized that OP didn't even prove Fisher-Yates. I blogged about this several weeks back, and here is an excerpt from it. Some of you might find it useful.
"This is easy to verify for N = 2: You are just flipping a coin to decide if you swap 1 with 2. For N > 2, you just need to show that each of 1 through N has an equal chance of getting the k-th slot for 1 through N. In the first step, every number has a 1/N probability of getting into the first slot. For all other slots: the number has (1-1/N) chance of getting/staying there, then by induction, all slots are equally likely, hence (1-1/N)*1/(N-1) = 1/N. This completes the proof."