Perfectly shuffling a deck of cards, over and over

I got a little curious about what happens to a deck of cards when you perfect-shuffle it N times, so I wrote some code to do it. I was a bit surprised that so much structure remained in the deck after the fourth shuffle. Stylistic criticism is most welcome.

#! /usr/bin/perl -w

use strict;
use Data::Dumper;

# this is ugly, and overkill
sub min
{
    my $x = shift;
    return $x if scalar @_ == 0;
    my $y = &min(@_);
    return $x > $y ? $y : $x;
}

sub perfect_shuffle
{
    my ($a, $b) = @_;

    my @res   = ();
    my $n_els = @$a;

    if(@$a != @$b) {
        warn "perfect_shuffle: lists must have equal length!\n";
        $n_els = &min(scalar @$a, scalar @$b);
    }

    while($n_els--) {
        push @res, shift @$a, shift @$b;
    }

    return \@res;
}

sub build_deck
{
    my $deck = ();

    for my $suit (('c', 'd', 'h', 's')) {
        for my $card ((2..9, 'T', 'J', 'Q', 'K', 'A')) {
            push @$deck, [$suit, $card];
        }
    }

    return $deck;
}

sub show_deck
{
    my ($deck) = @_;

    # print suits, then values
    # primo candidate for extraction into sub
    {
        local $\ = ' ';
        for (@$deck) { print $_->[0] }
    }
    print "\n";

    {
        local $\ = ' ';
        for (@$deck) { print $_->[1] }
    }
    print "\n";
}

sub split_deck
{
    my ($deck) = @_;

    my $mid = @$deck / 2;

    my @left  = @$deck[0..($mid-1)];
    my @right = @$deck[$mid..@$deck-1];

    return (\@left, \@right);
}

my $deck    = &build_deck();

for my $shuffle (1..10) {
    print "shuffle $shuffle:\n";
    my ($l, $r) = &split_deck($deck);
    $deck = &perfect_shuffle($l, $r);
    &show_deck($deck);
}
[download]

-- F o x t r o t U n i f o r m Found a typo in this node? /msg me % man 3 strfry

Comment on Perfectly shuffling a deck of cards, over and over Download Code

Replies are listed 'Best First'.
Re: Perfectly shuffling a deck of cards, over and over by blokhead (Monsignor) on Jul 10, 2004 at 00:35 UTC
This type of shuffle is called a Riffle shuffle. You have enough reading material to satisfy any curiousity about their mathematical properties in the Mathworld entry for Riffle Shuffle and its references (You'll see that it makes a difference if you do an in- or out- shuffle). japhy has a one-liner to do either-sided Riffle shuffles at Array One-liners. You can make this really succinct if you also use glob to generate the initial deck: `sub riffle { splice @_, @_/2 - $_, 0, pop for 0 .. (@_/2)-1; return @_; } my @deck = glob "{2,3,4,5,6,7,8,9,T,J,K,Q,A}{C,D,H,S}"; for my $shuffle (1 .. 10) { @deck = riffle @deck; print "shuffle #$shuffle:\n@deck\n"; }` [download] It might also be interesting to see what happens when you change the riffle sub to: `## random-sided Riffle shuffle sub riffle { if (rand() < 0.5) { splice @_, @_/2 - $_, 0, pop for 0 .. (@_/2)-1; } else { splice @_, @_/2 + $_, 0, shift for 0 .. (@_/2)-1; } return @_; }` [download] blokhead	[reply] [d/l] [select]
Re^2: Perfectly shuffling a deck of cards, over and over by Anonymous Monk on Jul 10, 2004 at 03:03 UTC
So, why does glob work here when those files most likely don't exist on your system. Skimming through the glob and File::Glob docs it seems like glob should only return valid file names. Its a great trick, and it works for me under Windows. Just curious why? Ted	[reply]
Re^3: Perfectly shuffling a deck of cards, over and over by Enlil (Parson) on Jul 10, 2004 at 05:31 UTC
Like Mr. Muskrat mentioned above, the documentation for glob mentions: In list context, returns a (possibly empty) list of filename expansions on the value of EXPR such as the standard Unix shell /bin/csh would do So one needs to look to find what the documentation for /bin/csh says. If you search around the web for csh documentation who will come across a section on "filename substitution" (aka globbing). In short what this documentation says is that if it contains a `"*", "?","[", or "~"` then it an error not to have any files match. On the other hand it mentions nothing of "{". It also mentions that something like "a{b,c,d}e" is metanotation for a shorthand way of writing "abe ace ade" which is the trick played above with the `glob` function to get a list of possible combinations of card values and suits, i.e.,: `my @deck = glob "{2,3,4,5,6,7,8,9,T,J,K,Q,A}{C,D,H,S}";` [download] HTH -enlil	[reply] [d/l] [select]
Re^3: Perfectly shuffling a deck of cards, over and over by Mr. Muskrat (Canon) on Jul 10, 2004 at 04:45 UTC
It's simple really. The glob documentation says that it performs filename expansion just like the standard Unix shell but it never says that it checks for those files to exist. It's only creating a list of possible filenames. It's up to you to figure out if they are there.	[reply]
Re: Perfectly shuffling a deck of cards, over and over by Discipulus (Canon) on Jul 12, 2004 at 09:24 UTC
I got the first shuffle eq to the 9th and the second eq to the 10th .... WHY ? only 3th to 8th suffles seems to be chaotic... it is correct ? cheers lorenzo* PS if I make 8 shffle only I get the orderd deck!	[reply]
Re^2: Perfectly shuffling a deck of cards, over and over by QM (Parson) on Jul 12, 2004 at 13:45 UTC
From the Mathworld reference above: An ordinary deck of 52 cards is returned to its original order after 52 in-shuffles, but after only eight out-shuffles! -QM -- Quantum Mechanics: The dreams stuff is made of	[reply]
Re^3: Perfectly shuffling a deck of cards, over and over by ChuckularOne (Prior) on Jul 23, 2004 at 12:03 UTC
The good news is that in the real (physical) world, it's much harder to shuffle the deck perfectly. There is also the additional fact that after playing a hand of anything, the deck is not in order to begin with. That is a little more difficult to simulate.	[reply]
Re: Perfectly shuffling a deck of cards, over and over by spurperl (Priest) on Jul 11, 2004 at 17:08 UTC
I guess this is why I'm never quite satisfied with Winamp's "randomization" of the playing list ;-)	[reply]