How would you write a shuffle algorithm?

As I'm beginning to write my card game application, I've approached the unit test where I need to shuffle the deck. I've implemented it based on Knuth's Shuffle algorithm. My question is, what are some clever ways that other programmers have implemented it?

My current implementation works like this.

Put all 52 cards in an array
For Loop starting at element 51, working backwards
Generate random number between 0 and loop element index
Swap current element card with the element at the random index generated in previous step
Finish when loop index reaches the zero element.

Delima with current implementation

Is there a bias with generating a random number between 0 and the loop index? I'm doing so with java.util.Random
Would multiple shuffle iterations over the deck solve this?
Is it worth refactoring the shuffle algorithm to use the strategy pattern so I can have multiple implementations of shuffle? After all, this is a simple command line game, not Harrah's next killer online gambling app.

Responses[24]

Posted by Mike Shoemaker on December 1, 2005 11:59:32 PM CST #

Re: How would you write a shuffle algorithm?

Comment from Anonymous on December 2, 2005 1:20:06 AM CST #

java.util.Collections.shuffle()

Re: How would you write a shuffle algorithm?

Comment from Anonymous on December 2, 2005 2:41:49 AM CST #

http://mathworld.wolfram.com/Shuffle.html

Re: How would you write a shuffle algorithm?

Comment from Anonymous on December 2, 2005 3:18:50 AM CST #

Is there something wrong with the java.utils.Collections shuffle method? http://java.sun.com/j2se/1.3/docs/api/java/util/Collections.html#shuffle(java.util.List)

Re: How would you write a shuffle algorithm?

Comment from Hans on December 2, 2005 9:43:07 AM CST #

It seems odd to consume the deck while shuffling like that. The cards at 0 and 1 have a 50% chance of being swapped twice, the one at 51 has no chance at all, the those between follow a linear trend between those probabilities. I'd have to think more about it, but it certainly seems that having such a pattern would be a weakness. I wonder how Collections.shuffle() does it...

Re: How would you write a shuffle algorithm?

Comment from Mike Shoemaker on December 2, 2005 10:01:48 AM CST #

The reason I chose to implement shuffle myself is all about fun. I do business apps for a living and getting back into the academic midset is fun. Besides I think it's an interesting problem and using Collections.shuffle() isn't fun regardless if it is more effective or not. I guess you could say I'm interested in thinking about the problem rather than solving it :) I found this Joel on Software link via google after posting this. Similar request with lot's of discussion. Some good, some bad. SNR is decent but not great.

Re: How would you write a shuffle algorithm?

Comment from Anonymous on December 2, 2005 12:38:14 PM CST #

Why not shuffle lke people do? Pick a index close to the middle of the deck and split then deck in to two smaller piles. Take the top card from each pile and randomly choose one to place back at the top of the deck and remove from the respective pile. Increase the odds of picking the card from the deck that wasn't chosen last time. Do this a couple of times. Next, pick a randomly sized pile from the middle of the deck for one pile and put the rest of the cards in the other pile. Place one pile in the deck, and then the other pile in the deck. Repeat this a few times. Finally, cut the deck.

Re: How would you write a shuffle algorithm?

Comment from Sandy McArthur on December 2, 2005 3:11:56 PM CST #

A lot of effort went into Collections.shuffle so that it was correct. It's easy to get this wrong so stick with the standard implementation.

Re: How would you write a shuffle algorithm?

Comment from Mike Wallace on December 2, 2005 7:28:13 PM CST #

This is an interesting problem I worked on a little while ago. I'll try to describe my solution here.

Let's say you want to shuffle the numbers 0 to 51 (each number referring to a card in your deck). First create an array of 52 booleans, setting each one to false (call this array b[]). Now generate a random number from 0 to 51 (inclusive). Call this number n. Update your array of booleans so that b[n] = true. The value of n is the first number in your shuffled list.

Generating subsequent entries for your shuffled list is handled slightly differently. First, decrement the upper value of your range of numbers, so the second number is between 0 and 50, and so forth. Once you have this number (let's call it m), find the mth entry in b[] which has a value of false. The index for that entry is the new value to add to your list of shuffled numbers. Mark that value of b[] as true. Repeat.

The process is simpler for the first step because all entries in b[] are false, so if your random number is, say, 3, you already know the 3rd entry of b[] is the 3rd false entry, so 3 is the first shuffled number. If the second random number is 3 again, then the second shuffled number is 4. In practice, things work slightly different since it's all zero-based.

I have code that demonstrates this, so let me know if you want a copy.

Re: How would you write a shuffle algorithm?

Comment from Anonymous on December 2, 2005 9:26:59 PM CST #

Mike, your code is wrong because it doesn't generate a perfectly random shuffle (it will generate a biased shuffle). It also does more work than necessary whenever it chases booleans that haven't been set to true yet (probability increases whenever the index goes up).

The implementation of the blog author is also wrong (or rather, overkill): you only need to loop until 26 to get a perfect shuffle.

Re: How would you write a shuffle algorithm?

Comment from Mike Wallace on December 2, 2005 9:43:52 PM CST #

How is my shuffle method biased? The numbers I get look evenly distributed. Is there an easy way to check if a series of collections of numbers show a bias?

Re: How would you write a shuffle algorithm?

Comment from Mike Shoemaker on December 2, 2005 10:17:46 PM CST #

First off, neither Mike or myself are wrong. Our implementations may not be the most optimal and they may or may not introduce bias. The point of the entry was to hear how others have done this kind of thing and have a bit of discussion about it.

Re: How would you write a shuffle algorithm?

Comment from Jay on December 2, 2005 10:51:33 PM CST #

Refactoring the shuffle algorithm is a great idea. Most of the things we do as developers helps us grow in knowledge and experience. This would do that, even if in a small way. You current implementation sounds fine. However, one change I'd make is to call setSeed on the Random instance you are using to the current time in Millis, just before a shuffle.

Re: How would you write a shuffle algorithm?

Comment from Simon Harris on December 2, 2005 10:59:26 PM CST #

A priority queue with a random comparator has always been perfectly acceptable for my use.

Re: How would you write a shuffle algorithm?

Comment from Anonymous on December 3, 2005 1:06:56 AM CST #

Mike: your shuffle is biased because you chase for unset bits by incrementing the index until you find one. To get a perfect shuffle, you should regenerate a random number instead. Which of course is way too expensive and will in average invoke random() 51! (factorial of 51) times. Like you say, the numbers only "look" evenly distributed. They are not, and it can be proven easily.

Here is a simple perfect shuffle:

for (int i = 0; i < 26; i++) { swap(a[i], a[random(52)] }

You can prove mathematically that it's a perfect shuffle (in average, you're guaranteed that all the cards in the deck will be shuffled over a large enough sample).

Exercise for the reader: why is 26 sufficient?

Re: How would you write a shuffle algorithm?

Comment from Andrew on February 7, 2008 5:08:17 PM CST #

These issues are all covered pretty well in the Wikipedia entries for Shuffling and the Knuth_shuffle. Swapping only 26 times clearly cannot produce a perfect shuffle by a pigeonhole argument.&nbsp;

If you do 26 swaps, each with 52 possibilities, you have 52^26 possible outcomes. However, there are 52! possible sequences for a deck, which is much larger than 52^26.&nbsp; Therefore, there are some sequences that your algorithm will never generate.

Andrew

Re: How would you write a shuffle algorithm?

Comment from Anonymous on March 12, 2008 9:13:38 AM CDT #

I was given this question for an interview and I went home and just took a first crack at it. This is what I intuitively came up with.

public

{

}

shuffledCards[counter] = next;

randomHistories.Add(next);

++counter;

}

iter =

}

static int[] Shuffle(int[] cards)int cardsCount = cards.Length;int[] shuffledCards = new int[cardsCount];IList<int> randomHistories = new List<int>(cardsCount);var counter = 0;var iter = true;var random = new Random();while (iter) {var next = random.Next(1, (cardsCount + 1));if (randomHistories.Contains<int>(next)) {continue;else {if (randomHistories.Count == cardsCount) {false;return shuffledCards;

Re: How would you write a shuffle algorithm?

Comment from Anonymous on December 3, 2005 1:08:35 AM CST #

Mike (the original poster): as I said, your algorithm is not wrong (it will generate a perfect shuffle) but it's not optimal.

The other Mike's algorithm is "wrong", though (in the sense that it will not generate a perfect shuffle, which I assumed was your goal).

Re: How would you write a shuffle algorithm?

Comment from Anonymous on December 3, 2005 1:09:52 AM CST #

Mike (the poster): actually, your algorithm is wrong too :-)

You should always pick random(52) and not random(i), or you will find that your values are indeed not evenly distributed.

Re: How would you write a shuffle algorithm?

Comment from Ron on December 5, 2005 12:21:42 PM CST #

Mike's algorithm is the same as Collections.shuffle. Nothing is wrong with it. It is not worth using the strategy pattern for this case. Do not update your seed between card swaps. Chances are the system timer will alias and you will get lots of duplicates in your number sequence. For more randomness, augment your seed with noisy information from the system or user, but what you've done so far is perfect for a simple card game.

Re: How would you write a shuffle algorithm?

Comment from Jon Tirsen on December 7, 2005 11:33:29 PM CST #

Slightly off-topic but this is shuffle in Ruby: cards.sort_by{|i| rand} Try it out here: http://tryruby.hobix.com/

Re: How would you write a shuffle algorithm?

Comment from Anonymous on February 3, 2006 6:30:06 PM CST #

"Exercise for the reader: why is 26 sufficient?" It is not. It may be on average, but theoretically all cards >=26 can still be in perfect order.

Re: How would you write a shuffle algorithm?

Comment from Anonymous on March 18, 2007 12:55:42 AM CDT #

tell me i'm wrong, but aren't you all thinking too much about this? it all depends on the random() function you choose. designing random() is waaaay beyond my scope, but assuming you're using the best implementation of random() then shuffle() writes itself. simply pick an element at random and put it in a new array. repeat until all elements exhausted. - yes, this means having two arrays.... so lets focus on writing an algorithm to use one array. i still think the simplest and 'most' correct way is: traverse the array swap each element with a random element and it's as simple as that.

Re: How would you write a shuffle algorithm?

Comment from Matthew Turland on January 27, 2008 2:21:04 PM CST #

Consider representing the deck with a directional graph where each node has an edge pointing to and away from it with the exception of two, namely the bottom and top cards. Have a flag for each edge representing whether or not that edge has been modified with respect to the original graph.

Pick a random node in the graph and change its edge to point to a node that does not already have an edge pointing to it, which in the case of the first iteration with be either the bottom or top card. Set the flag on that edge so you know it's been changed. At this point, repeat the process of changing edges to point to other nodes that do not have edges pointing to them. Do this until all edges have been flagged as changed. This will ensure that no card in the deck is adjacent to any cards to which it was previously adjacent in the original deck configuration.

Re: How would you write a shuffle algorithm?

Comment from Anonymous on March 14, 2008 9:00:10 PM CDT #

I had posted this earlier but did not do a preview.

public static int[] Shuffle(int[] cards)
{
var cardsCount = cards.Length;
int[] shuffledCards = new int[cardsCount];
var counter = 0;
var iter = true;
var random = new Random();

while (iter)
{
var randomIndex = (random.Next(1, (cardsCount + 1)) - 1);
var card = cards[randomIndex];

if (shuffledCards.Contains<int>(card))
{
continue;
}

else
{
shuffledCards[counter] = card;
++counter;
}

if (counter == cardsCount)
{
iter = false;
}

}
return shuffledCards;
}

Add a comment

December 2005
Sun	Mon	Tue	Wed	Thu	Fri	Sat
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31
Nov \| Today \| Jan