Re: Can random_shuffle be used to shuffle a deck of cards?

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance

"Alex Blekhman" <tkfx.REMOVE@xxxxxxxxx> wrote in message
news:%23FNq6kDAIHA.5360@xxxxxxxxxxxxxxxxxxxx
Daniel Lidstrom wrote:
I recently read that in order to shuffle a deck of 52 cards, you
would need a random number generator with a perion greater than 52!
(about 10^67). How can the implementation of random_shuffle
guarantee to pick one of the 52! permutations? Let's say I shuffle
100 items (10^157 permutations), can random_shuffle still do it
correctly? How does the algorithm overcome the limitations of rand()?

Actually, for `std::random_shuffle' it's enough that `rand'
(or user provided function) returns a number 0 <= N < 52 in
order to shuffle an array of 52 elements. The implementation
of `std::random_shuffle' uses Fisher-Yates shuffle:

"Fisher-Yates shuffle"
http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

Quoting from this article:

Limited PRNG state space
An additional problem occurs when the Fisher-Yates shuffle is used with
a pseudorandom number generator: as the sequence of numbers output by
such a generator is entirely determined by its internal state at the
start of a sequence, a shuffle driven by such a generator cannot
possibly produce more distinct permutations than the generator has
distinct possible states. Even when the number of possible states
exceeds the number of permutations, the irregular nature of the mapping
from sequences of numbers to permutations means that some permutations
will occur more often than others. Thus, to minimize bias, the number of
states of the PRNG should exceed the number of permutations by at least
several orders of magnitude.

For example, the built-in pseudorandom number generator provided by many
programming languages and/or libraries may often have only 32 bits of
internal state, which means it can only produce 2^32 different sequences
of numbers. If such a generator is used to shuffle a deck of 52 playing
cards, it can only ever produce a vanishingly small fraction of the 52!
? 2^225.6 possible permutations. Thus, it's impossible for a generator
with less than 226 bits of internal state to produce all the possible
permutations of a 52-card deck, and for a (reasonably) unbiased shuffle,
the generator ought to have at least about 250 bits of state.

--
With best wishes,
Igor Tandetnik

With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925


.

Relevant Pages

  • Re: Can random_shuffle be used to shuffle a deck of cards?
    ... I recently read that in order to shuffle a deck of 52 cards, ... The algorithm makes no attempt to overcome randlimitations. ... Assuming you start with a sorted list, depending on your random number generator, some orderings may never appear. ...
    (microsoft.public.vc.stl)
  • Re: Use of random bits
    ... On the other hand the Mersenne Twister Random Number Generator used e.g., in SPSS, is considered a very good one for many purposes. ... will it be one chosen with equal probability from all permutations. ... end input program. ...
    (sci.stat.math)
  • Re: bijective mapping function question
    ... i am writing an application that needs to list all possible ... permutations of an n bit sequence, where n is a large number, ... Why not just use a random number generator to "shuffle the deck". ...
    (sci.math)
  • Re: shuffling algorithm
    ... iteration, the random number generator is asked to pick an integer in. ... your algorithm is a mapping of a set of 27 equal probability items ... (the possible sequences of 3 numbers in generated by the random number ... generator) onto a set of 6 items (the possible permutations of 3 cards). ...
    (sci.crypt)
  • Re: quick algorithm for random permutation
    ... the [Knuth shuffle] works because, ... sequences generated by a sufficiently pseudorandom generator. ... individual elements to be shuffled are distinct, each sequence will ...
    (comp.theory)