How to simulate REAL card shuffling?

[ericvw]

How would I shuffle a static array of 52 cards that you input an
integer, n, into a function and it takes the first n cards as the left
segment and the remaining as the right. Then it shuffles this deck
starting from the first of the right segment, then first of the left,
second of the right, second of the left. Once one side is exhausted it
fills in the rest of the shuffle with the other remaining segment. Any
suggestions?

 

[opalpa]

The algorithm could be:
let L be left segment
let R be right segment
let S be empty segment that will get shuffled cards
merge L and R onto S

There is a problem in that you did not request any randomness. That is
to get cards shuffled the merge should randomly pick an element off
front of L or R.

Opalinski
(e-mail address removed)
http://www.geocities.com/opalpaweb/

 

[Eric VW]

I don't want randomness. I want to take the front of each R then L
segment, alternating until one of the L or R segments is exhausted. I
was able to get that part done. But now...I don't know how to
implement tagging on the rest of the leftover segment. Because the
deck may nut be cut down the middle.

 

[Alan Johnson]

How would I shuffle a static array of 52 cards that you input an
integer, n, into a function and it takes the first n cards as the left
segment and the remaining as the right. Then it shuffles this deck
starting from the first of the right segment, then first of the left,
second of the right, second of the left. Once one side is exhausted it
fills in the rest of the shuffle with the other remaining segment. Any
suggestions?

This is more of an algorithms problem than a C++ problem, but it was fun
to think about. First, are you allowed to use external storage? If so
the problem becomes pretty easy. Just follow the algorithm outlined in
opalpa's response.

If, however, you need an "in place" algorithm, things get a little bit
more complicated. I propose the following algorithm for when the total
number of cards is a power of 2. Fixing it to work with any number of
cards is an implementation detail I'll leave to you. The intuition is
as follows. When the algorithm completes, the first half of the array
will be composed of the first and third quarters of the original array.
Likewise, the last half of the array will be composed of the second and
fourth quarters of the original array. So, for our first step we'll
swap the second and third quarter. We've now reduced the problem into
two problems of half the size. The base case in this algorithm is a
problem of size 2, which is correctly shuffled without doing anything.
So, the whole algorithm looks like:

Shuffle(array A)
if (size of A > 2)
swap(second quarter of A, third quarter of A)
Shuffle(first half of A)
Shuffle(second half of A)

How fast is it? The swap takes O(N) time (where N is the total number
of cards). And you have two subproblems of size N/2. So, by the Master
Theorem the running time is bounded by O(N log N).

If you have a specific problem with implementing this (or whatever
solution you choose) in C++, come back and I'm sure someone will be
happy to help further.

-Alan

 

[Daniel T.]

I don't want randomness. I want to take the front of each R then L
segment, alternating until one of the L or R segments is exhausted. I
was able to get that part done. But now...I don't know how to
implement tagging on the rest of the leftover segment. Because the
deck may nut be cut down the middle.

By all means, show us the code you have so far...

 

[Eric VW]

where DeckSize = 52;

void
Deck::shuffle(int n)
{
Card tmp[DeckSize];
int i;

for(i = 0; i < (DeckSize - n); i++) {
tmp[i*2] = deck[n + i];
tmp[(i*2) + 1] = deck;
}

for(int j = i*2; j < DeckSize; j++) {
temp[j] =

}

 

[Eric VW]

Card tmp[size];

for(int i = 0; i < (DeckSize - n); i++) { //here is the merger part
tmp[i*2] = deck[n + i];
tmp[(i*2) + 1] = deck;
}

 

[Daniel T.]

where DeckSize = 52;

void
Deck::shuffle(int n)
{
Card tmp[DeckSize];
int i;

for(i = 0; i < (DeckSize - n); i++) {
tmp[i*2] = deck[n + i];
tmp[(i*2) + 1] = deck;
}

for(int j = i*2; j < DeckSize; j++) {
temp[j] =

}

Try solving it by maintaining three indexes instead of just doing
everything with one index. One index into the tmp array, one index
starts from the beginning of the deck and goes to n, the third index
starts from n and goes to DeckSize.

With two indexes into the deck, you will be able to tell which end
finishes first.

Here is what I came up with:

template < typename FwIt, typename OutIt >
void shuffle( FwIt pile1, FwIt pile2, FwIt end, OutIt result )
{
FwIt pile1end = pile2;
while ( pile1 != pile1end && pile2 != end ) {
*result++ = *pile1++;
*result++ = *pile2++;
}
while ( pile1 != pile1end )
*result++ = *pile1++;
while ( pile2 != end )
*result++ = *pile2++;
}

The tests below show how to use the function. It will work with any of
arrays, vectors, deques, or lists. If you want to deal with indexes
instead, you'll have to make modifications.

test_(card_shuffle_4) {
vector<int> cards( 4 );
for ( int i = 0; i < cards.size(); ++i )
cards = i;
const int cut_point = 2;
vector<int> shuffled;
shuffle( cards.begin(), cards.begin() + cut_point, cards.end(),
back_inserter( shuffled ) );
failUnlessEqual( shuffled.size(), 4 )
failUnlessEqual( shuffled[0], 0 );
failUnlessEqual( shuffled[1], 2 );
failUnlessEqual( shuffled[2], 1 );
failUnlessEqual( shuffled[3], 3 );
}

test_(card_shuffle_5_cut_3)
{
vector<int> cards( 5 );
for ( int i = 0; i < cards.size(); ++i )
cards = i;
const int cut_point = 3;
vector<int> shuffled;
shuffle( cards.begin(), cards.begin() + cut_point, cards.end(),
back_inserter( shuffled ) );
failUnlessEqual( shuffled.size(), 5 )
failUnlessEqual( shuffled[0], 0 );
failUnlessEqual( shuffled[1], 3 );
failUnlessEqual( shuffled[2], 1 );
failUnlessEqual( shuffled[3], 4 );
failUnlessEqual( shuffled[4], 2 );
}

test_(card_shuffle_5_cut_2)
{
vector<int> cards( 5 );
for ( int i = 0; i < cards.size(); ++i )
cards = i;
const int cut_point = 2;
vector<int> shuffled;
shuffle( cards.begin(), cards.begin() + cut_point, cards.end(),
back_inserter( shuffled ) );
failUnlessEqual( shuffled.size(), 5 )
failUnlessEqual( shuffled[0], 0 );
failUnlessEqual( shuffled[1], 2 );
failUnlessEqual( shuffled[2], 1 );
failUnlessEqual( shuffled[3], 3 );
failUnlessEqual( shuffled[4], 4 );
}

 

[Howard]

I don't want randomness. I want to take the front of each R then L
segment, alternating until one of the L or R segments is exhausted. I
was able to get that part done. But now...I don't know how to
implement tagging on the rest of the leftover segment. Because the
deck may nut be cut down the middle.

Just a side note (which won't help solve your problem at all, sorry):

If you don't have randomness, then you don't have a "real" card shuffle, you
have a "perfect" card shuffle.

When a person actually shuffles, the number of cards coming from the left
and the right pile aren't always exactly 1 (except maybe for some really hot
card handlers). That's what provides randomness, making the result after
several shuffles be at least failry unpredictable.

If exactly 1 card is always added from the left and then the right, then
it's not really worth shuffling, because one can predict where there cards
will end up. In fact, if you always cut the deck exactly in half, and
always have a "perfect" shuffle as described, then after 8 shuffles, the
deck will be back in exactly the same state it was before shuffling!

That's why shuffling is done in a completely different manner in software...
so that there is truly some sort of randomness introduced to the result.

-Howard