Analysis of a Brute-Force Shuffle

freefour.com

15 pointsluu4 comments

Card shuffling is one of those situations where there's a very well known and fairly unambiguously "right" answer.

I honestly thought it was well known enough that there wouldn't be any sense in writing an article about it, but I guess I should focus on being excited for the author for being one of today's 10,000 [1], rather than judgemental that they didn't know it before. Incidentally, this is a good reason to not use deck shuffling as an interview question. If they happen to know the right answer (which isn't unlikely) then there's no value gained in asking them.

[1] http://xkcd.com/1053/

You didn't cover the expected randomness of distribution of cards with each algorithm which can be the most important factor. And what does "properly shuffled" mean?

For some nice charts and pictures, you can see the original blog post this one was inspired by: http://datagenetics.com/blog/november42014/index.html It contains pictures for an algorithm that doesn't properly shuffle, as well as the fisher-yates shuffle.

The distribution is the same for both... in this case "properly shuffled" obviously means an uniform distribution over all shuffles.

Reply on news.ycombinator.com