Hacker News Reader

Comment by allenbrunson | Hacker News Reader

I just happen to have implemented something like this myself recently, which seems easier to me. here it is: generate a large random number for each card, then sort the list according to the random numbers. Can anybody here poke holes in that one?

View on HN

It's O(N * log(N)) instead of O(N).

And of course it has the usual problem of generating permutations using a pseudo random number generater: Even for moderately sized collections, the number of permutations is far larger than the number of differnt initialization states of many common PRNGs, so even if an algorithm looks correct, it may not be able to generate all permutations. For example, a 63 bit linear congruential shift generator has 2^63 = 9x10^18 possible sequences, while there are about 52! = 80x10^66 permutations of 52 cards.

i'm not really worried about the complexity. it's plenty fast enough for my needs. but i am worried about getting decent results. i suck at anything that smells like math, but i think you're saying that the distribution of random numbers might not be random enough to get decent results, right?

is there some random number generator in a C-like language i should investigate, as opposed to using srand() and rand()?

Just read volume 4 of TAoCP when it appears in print :-).

Actually, if your game is not about real money, this problem might be more of an academic curiosity, but there are some algorithms with very long periods, start at one of these pages to look for an algorithm with weaknesses that you can live with:

- http://en.wikipedia.org/wiki/Mersenne_twister

- http://en.wikipedia.org/wiki/Blum_Blum_Shub

- http://en.wikipedia.org/wiki/Pseudorandom_number_generator

distribution of random numbers might not be random enough to get decent results, right?

This is a problem, but it will be a problem no matter what algorithm you choose. You can always use something like http://www.random.org/ or special hardware, but I'd just look to /dev/random and whatever your default psudo-random generator is for your platform.

You probably have something like 2^32 ways to seed your RNG. But there are N! possible outcomes of the shuffle, so at most 2^32 of those will appear (one per seed).

2^32 = 4294967296

100! is about 10^158

So for just 100 items, you're already missing most of your outcome space. You might switch to a generator with a bigger seed. For this example with 100 items, you need at least

log(100 !) / log(2) = 524.764993

bits in your seed. For N items to be sorted, you need about NlogN bits in your seed. So if you're trying to actually make each outcome possible, then no matter which clever algorithm you use to go from random numbers to a shuffled sequence, you've already lost.

hrm. never thought of it that way before. but assuming I seed the prng only once at the beginning of a program run, i could hit every possible shuffle on subsequent deals, couldn't I?

No, you couldn't, that's what this subthread is about. A PRNG with 32 bit entropy will only ever produce 2^32 different sequences of random numbers and so only 2^32 different shuffles. If you want more, you must introduce more entropy, either by using a larger PRNG, or using a hardware RNG. Calling the same PRNG fro diffferent threads (don't forget your synchronization primitives!) might also work as a cheap source of entropy but will likely have either bad statistical properties or horrible performance: for it to make a real difference, every single shuffle of a deck must be interspersed with many calls to the PRNG from other threads. If calls from other threads do only happen between shuffles, all you gain from introducing shared state concurrency into your program is that the same 2^32 permutations are generated in a different order.

But, as I remarked earlier, if this is just for a game that is for fun where opponents can't cheat you or other players out of large amounts of money by predicting which permutations may or may not occurr, you may get away with whatever PRNG you have at hand and only swap is out once many players start to complain that they had this very hand one or two billon games ago.

You could exploit the fact that you're sorting numbers and get a better time complexity:

http://en.wikipedia.org/wiki/Radix_sort

http://en.wikipedia.org/wiki/Bucket_sort

That problem (not enough entropy in your PRNG state) isn't specific to the particular way of shuffling: it applies just the same if you do a Fisher-Yates shuffle, for instance.

Besides the performance difference, the main issue is the ideal of a perfect shuffle: each of the N! sorts ought to be equally likely.

(N.b.: this post ended up being mostly the same point as fhars, only phrased differently.)

However, this is tricky to achieve. It requires either:

- an infinite source of random numbers

- a psuedo random number generator whose pool size (the # of random numbers it can generate) is an even multiple of N! (If not, then it have bias towards certain shuffles almost by definition.)

Here's what happens when someone does it all wrong -- the wrong shuffle algorithm and, far more devastatingly, a poor PRNG choice:

http://www.cigital.com/papers/download/developer_gambling.ph...

(Consider that if your PRNG takes a 32-bit seed, there will be at most be 2^32 possible shuffles, even with a correctly perfect shuffling algorithm --- few enough for an attacker to pre-calculate every possible shuffle to use against you.)

A problem can occur if you're shuffling a large number of cards (greater than the maximum of the random number generator) because each random number should be unique.

Reply on news.ycombinator.com