Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I learned of the Fisher-Yates shuffle as the Knuth shuffle, but apparently both names are used for it.

http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle



I have used an alternate shuffling approach in the past of my own naive creation, which is to go from 1-N items, each pass selecting a random number to swap the current position with. This would not require counting over missing items (those copied to result) on each loop. What is the flaw in this approach I wonder?


I've used that method too. The flaw is that it is biased; some permutations will be more likely than others.

Each shuffle will consume N random numbers between 1 and N (inclusive). This gives a total of N^N equally probable N-tuples of random numbers, all corresponding to exactly one output permutation.

But there are only N! possible permutations, so some of the N^N N-tuples must share the same output permutation. Since N! does not usually divide N^N evenly, some permutations must be more probable than others.


Ah....clever. thx.




Consider applying for YC's Summer 2026 batch! Applications are open till May 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: