shuffling

I was surprised to learn that pseudo random number generators cannot shuffle a deck of cards.

Well, some can.

But some can't.

Many pseudo random number generators work as follows: they keep some 32-bit number, and each time a new random number is requested, they modify the number in some fancy way, and then return it. The algorithm can be "seeded" by specifying which number to start with.

If such an algorithm is used to shuffle some cards, the shuffling will be the same if the same seed is used. Since there are only 2³² possible seeds, there must be only 2³² possible shufflings.

However, a 52 card deck can be ordered in 52! (factorial) possible ways, which is about 2²²⁶. Hence, any pseudo random number generator with less than 2²²⁶ possible seeds cannot produce all possible shufflings.

In fact, if the pseudo random number generator has only 2³² seeds, then we can probably predict the order of the entire deck after observing the first 6 cards, since 52!/(52 - 6)! > 2³². Another way of saying this is that with 2³² seeds, we can't even generate all possible 6-card sequences. Of course, the shuffling algorithm might always put the same 6 cards in front, and shuffle the rest, so that's why I say we can probably predict the rest of the cards by knowing the first 6, because the shuffling algorithm is probably not doing something stupid like that.