Re: Swapping is inefficient and wasteful
From: Brian Hetrick (bhetrick_at_notinnedmeats.iname.com)
Date: 11/23/04
 Next message: Bill Unruh: "Re: Is reverse engineering legal ?"
 Previous message: Joe Peschel: "Re: Is reverse engineering legal ?"
 Next in thread: Paul Tomkins: "That is not the algorithm I proposed"
 Reply: Paul Tomkins: "That is not the algorithm I proposed"
 Reply: MokKong Shen: "Re: Swapping is inefficient and wasteful"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
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."
 Next message: Bill Unruh: "Re: Is reverse engineering legal ?"
 Previous message: Joe Peschel: "Re: Is reverse engineering legal ?"
 Next in thread: Paul Tomkins: "That is not the algorithm I proposed"
 Reply: Paul Tomkins: "That is not the algorithm I proposed"
 Reply: MokKong Shen: "Re: Swapping is inefficient and wasteful"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
