Thursday, October 14, 2010

Shuffling cards in PHP

The following demonstrates what I believe to be an efficient means of shuffling a deck of cards, using PHP.




$cards = array(array('suit'=>'Spade', 'rank'=>'01'), array('suit'=>'Spade', 'rank'=>'02'), array('suit'=>'Spade', 'rank'=>'03'), array('suit'=>'Spade', 'rank'=>'04'), array('suit'=>'Spade', 'rank'=>'05'), array('suit'=>'Spade', 'rank'=>'06'), array('suit'=>'Spade', 'rank'=>'07'), array('suit'=>'Spade', 'rank'=>'08'), array('suit'=>'Spade', 'rank'=>'09'), array('suit'=>'Spade', 'rank'=>'10'), array('suit'=>'Spade', 'rank'=>'11'), array('suit'=>'Spade', 'rank'=>'12'), array('suit'=>'Spade', 'rank'=>'13'), array('suit'=>'Spade', 'rank'=>'14'),
               array('suit'=>'Club', 'rank'=>'01'), array('suit'=>'Club', 'rank'=>'02'), array('suit'=>'Club', 'rank'=>'03'), array('suit'=>'Club', 'rank'=>'04'), array('suit'=>'Club', 'rank'=>'05'), array('suit'=>'Club', 'rank'=>'06'), array('suit'=>'Club', 'rank'=>'07'), array('suit'=>'Club', 'rank'=>'08'), array('suit'=>'Club', 'rank'=>'09'), array('suit'=>'Club', 'rank'=>'10'), array('suit'=>'Club', 'rank'=>'11'), array('suit'=>'Club', 'rank'=>'12'), array('suit'=>'Club', 'rank'=>'13'), array('suit'=>'Club', 'rank'=>'14'),
               array('suit'=>'Diamond', 'rank'=>'01'), array('suit'=>'Diamond', 'rank'=>'02'), array('suit'=>'Diamond', 'rank'=>'03'), array('suit'=>'Diamond', 'rank'=>'04'), array('suit'=>'Diamond', 'rank'=>'05'), array('suit'=>'Diamond', 'rank'=>'06'), array('suit'=>'Diamond', 'rank'=>'07'), array('suit'=>'Diamond', 'rank'=>'08'), array('suit'=>'Diamond', 'rank'=>'09'), array('suit'=>'Diamond', 'rank'=>'10'), array('suit'=>'Diamond', 'rank'=>'11'), array('suit'=>'Diamond', 'rank'=>'12'), array('suit'=>'Diamond', 'rank'=>'13'), array('suit'=>'Diamond', 'rank'=>'14'),
               array('suit'=>'Heart', 'rank'=>'01'), array('suit'=>'Heart', 'rank'=>'02'), array('suit'=>'Heart', 'rank'=>'03'), array('suit'=>'Heart', 'rank'=>'04'), array('suit'=>'Heart', 'rank'=>'05'), array('suit'=>'Heart', 'rank'=>'06'), array('suit'=>'Heart', 'rank'=>'07'), array('suit'=>'Heart', 'rank'=>'08'), array('suit'=>'Heart', 'rank'=>'09'), array('suit'=>'Heart', 'rank'=>'10'), array('suit'=>'Heart', 'rank'=>'11'), array('suit'=>'Heart', 'rank'=>'12'), array('suit'=>'Heart', 'rank'=>'13'), array('suit'=>'Heart', 'rank'=>'14'));
$shuffled_cards = array();
while (sizeof($cards) != 0)
{
  mt_srand((double)microtime()*1000000);
  $card = mt_rand(0, sizeof($cards) - 1);
  $shuffled_cards[] = $cards[$card];
  unset($cards[$card]);
  $cards = array_values($cards);
}
print_r($shuffled_cards);


We start by initializing our deck of fifty-two cards.  Each member of our array is an associative array holding the suit and rank of each card.  We then initialize a blank array where we will store our shuffled cards.
The while loop will execute until all of the cards have been popped out of our initial array.
At the beginning of each iteration we start a new pseudo-random seed.  Then, we get a random number between zero, and the number of cards we have left to shuffle, minus one (because arrays are zero indexed.)  Next, we append the randomly selected card to our shuffled array and remove it from our cards array.
When we remove a card from our numerically indexed array, the array becomes sparse.  So if the random number was four, then we are left with indexes one, two, three, five, six and so on.  If we hit four through another iteration, there would be no value to add to our shuffled array.
To make our array dense again, we can simply call the array_values function on our cards array and assign it back to cards.
This solution buys us a few niceties, compared to other solutions I have come across.  First, at any given time a card is only in one array (except the split moment that we are doing the move).  The second is that we don't have to worry about our random number being the same as a previously picked random number, and thus waste time picking another number until we hit a unique number.
Finally, this solution is really just an exercise in efficiently shuffling an array.  In a real application I would not use this solution at all.  PHP comes with a nice little function named, easy enough to remember, shuffle().  So let's take a look at how one should really implement the solution.


$cards = array(array('suit'=>'Spade', 'rank'=>'01'), array('suit'=>'Spade', 'rank'=>'02'), array('suit'=>'Spade', 'rank'=>'03'), array('suit'=>'Spade', 'rank'=>'04'), array('suit'=>'Spade', 'rank'=>'05'), array('suit'=>'Spade', 'rank'=>'06'), array('suit'=>'Spade', 'rank'=>'07'), array('suit'=>'Spade', 'rank'=>'08'), array('suit'=>'Spade', 'rank'=>'09'), array('suit'=>'Spade', 'rank'=>'10'), array('suit'=>'Spade', 'rank'=>'11'), array('suit'=>'Spade', 'rank'=>'12'), array('suit'=>'Spade', 'rank'=>'13'), array('suit'=>'Spade', 'rank'=>'14'),
               array('suit'=>'Club', 'rank'=>'01'), array('suit'=>'Club', 'rank'=>'02'), array('suit'=>'Club', 'rank'=>'03'), array('suit'=>'Club', 'rank'=>'04'), array('suit'=>'Club', 'rank'=>'05'), array('suit'=>'Club', 'rank'=>'06'), array('suit'=>'Club', 'rank'=>'07'), array('suit'=>'Club', 'rank'=>'08'), array('suit'=>'Club', 'rank'=>'09'), array('suit'=>'Club', 'rank'=>'10'), array('suit'=>'Club', 'rank'=>'11'), array('suit'=>'Club', 'rank'=>'12'), array('suit'=>'Club', 'rank'=>'13'), array('suit'=>'Club', 'rank'=>'14'),
               array('suit'=>'Diamond', 'rank'=>'01'), array('suit'=>'Diamond', 'rank'=>'02'), array('suit'=>'Diamond', 'rank'=>'03'), array('suit'=>'Diamond', 'rank'=>'04'), array('suit'=>'Diamond', 'rank'=>'05'), array('suit'=>'Diamond', 'rank'=>'06'), array('suit'=>'Diamond', 'rank'=>'07'), array('suit'=>'Diamond', 'rank'=>'08'), array('suit'=>'Diamond', 'rank'=>'09'), array('suit'=>'Diamond', 'rank'=>'10'), array('suit'=>'Diamond', 'rank'=>'11'), array('suit'=>'Diamond', 'rank'=>'12'), array('suit'=>'Diamond', 'rank'=>'13'), array('suit'=>'Diamond', 'rank'=>'14'),
               array('suit'=>'Heart', 'rank'=>'01'), array('suit'=>'Heart', 'rank'=>'02'), array('suit'=>'Heart', 'rank'=>'03'), array('suit'=>'Heart', 'rank'=>'04'), array('suit'=>'Heart', 'rank'=>'05'), array('suit'=>'Heart', 'rank'=>'06'), array('suit'=>'Heart', 'rank'=>'07'), array('suit'=>'Heart', 'rank'=>'08'), array('suit'=>'Heart', 'rank'=>'09'), array('suit'=>'Heart', 'rank'=>'10'), array('suit'=>'Heart', 'rank'=>'11'), array('suit'=>'Heart', 'rank'=>'12'), array('suit'=>'Heart', 'rank'=>'13'), array('suit'=>'Heart', 'rank'=>'14'));
shuffle($cards);
print_r($cards);