Re: Swapping is inefficient and wasteful

From: Brian Hetrick (bhetrick_at_notinnedmeats.iname.com)
Date: 11/23/04 

Date: Mon, 22 Nov 2004 22:51:59 -0500

"Paul Tomkins" <tomkinsp@iinet.net.au> wrote ...
[snip]

The algorithm you propose, deckB [i] = deckA [rand [i]], needs rand
[i] to do sampling without replacement. Otherwise, deckB has multiples
of some cards and therefore does not have other cards. The overhead of
keeping track of which cards have and have not been used essentially
duplicates the swapping necessary for shuffling a single deck.

I seem to recall from a course long ago that the algorithm (WARNING,
air code follows):

    card d [52];
    int i;
    for (i = 0; i < 52; i ++)
    {
        d [i] = (card) i;
    }
    for (i = 0; i < 52; i ++)
    {
        card t;
        k = (int) (rand () * 52);
        t = d [i];
        d [i] = d [k];
        d [k] = t;
    }

does not generate all possible permutations with equal probabilities,
but I remember proving the algorithm:

    card d [52];
    int i;
    for (i = 0; i < 52; i ++)
    {
        d [i] = (card) i;
    }
    for (i = 0; i < 51; i ++)
    {
        card t;
        k = i + (int) (rand () * (52 - i));
        t = d [i];
        d [i] = d [k];
        d [k] = t;
    }

does. The difference is that in the second algorithm, the swap of
element [i] is always with an element at position i or after. (In both
cases, rand () is assumed to produce a U[0,1) variate.)

Just about any elementary probability text would have an algorithm for
random shuffling, but the second algorithm above is, as far as I know,
"standard."

Relevant Pages

  • Re: Call for review: Hashing by hand algorithm
    ... perform my first algorithm, I'm very weary of over complicating it. ... but that defeats the simplicity of the "deck of cards" ... I re-hash the resulting deck. ... and the second instance encountered is the "second instance". ...
    (sci.crypt)
  • Re: Online poker and RNG...
    ... Second, as soon as the hole cards are dealt, ... of those five cards, what seeds are possible. ... site publishes its algorithm, in which case the missing ingredient is ... it is difficult to keep these algorithms totally secret -- ...
    (sci.crypt)
  • Re: Call for review: Hashing by hand algorithm
    ... perform my first algorithm, I'm very weary of over complicating it. ... but that defeats the simplicity of the "deck of cards" ... I re-hash the resulting deck. ... and the second instance encountered is the "second instance". ...
    (sci.crypt)
  • Re: Online poker RNG...
    ... Many sites use an RNG algorithm based on 2^32. ... even find one that accurately matched the cards dealt during several ... games of poker. ... each player gets two cards and three face-up cards ...
    (sci.math)
  • Re: suspicious or paranoid ??
    ... no other indications at the table, a majority of players at a given table can ... the site's clock that was used to shuffle and deal ... ... Another flaw in a different algorithm ... ... knowing your hole cards allowed the enterprising computer expert ... ...
    (rec.gambling.poker)