"Sam" wrote to ask about dealing a random set of cards from a deck. He said he was "attached and amused" by the About Visual Basic site. I'm not sure if that was a compliment or not, but I'll assume it was.
Sam said he had searched high and low on the web for the answer and there are incorrect answers out there. In Sam's case, he wants to generate a random sequence of 144 cards for Mah-Jong. It's easy to simply generate 144 random integers, but it's likely that some of them would be duplicates so you have to find a way to prevent that. Some of the answers don't take this into account.
I did my own web search and found two methods that were suggested to generate an array of unique integers. I wrote this basic article that covered those two methods. But over the next several weeks, some really talented programmers contributed content that went much deeper into the question. John McIlhinney contributed another method using lambda expressions and collections, a technology introduced with .NET 3.5. This turned out to be a fascinating analysis so I added a whole new article based on John's suggestions. You can find that article here.
But the most amazing study of the problem was done by "Chris". He wasn't content to simply look at various VB algorithms. Chris contributed an analysis that included a study of the distribution of the deal and an even more sophisticated method called the Fisher Yates algorithm. As a bonus, Chris's code also demonstrates (yet again!) why object oriented programming works. You can access the third article here.
But even that wasn't enough for Chris. He sent me a second email where he wrote, "I just can't leave this alone." He decided to compare the performance and features of VB and C# in solving this problem and provided what must be the most definitive analysis of this problem that exists on the web. Chris's contributions require some dedicated study to get through, but it's worth the effort. The fourth article is here.
Getting back to the basic question Sam had, he was aware of one of the ways of generating unique random integers: Just check to see if a number has already been generated and generate a new one if it has. He wrote that he didn't want to use this method because it was "unprofessional and messy in coding". The second method is to create an ordered array of integers (from 1 to the maximum) and then "shuffle" the numbers randomly. I decided to find out which way is the easiest to code and runs fastest.
Something that most pages don't mention is that these methods simply assume that the distribution of cards is something close to a truely random array. "Chris" shows that the "shuffle" method used here is not truely random in the third article. So use the "shuffle" code only if you're not too concerned about a really random distribution.
The code to generate a random array of integers by checking for duplicates isn't too messy. Here's what I came up with:
Dim Cards() As Integer Dim theSize = 52 Cards = Enumerable.Repeat(0, theSize).ToArray() Dim Tmp As Integer Randomize() Dim i As Integer = 0 Do While i < theSize Tmp = Int((theSize + 1) * Rnd()) If Array.IndexOf(Cards, Tmp) < 0 Then Cards(i) = Tmp ListBox1.Items.Add(Tmp) i += 1 End If Loop
The variable theSize is the size of the array. In Sam's case, it would be 144. Checking for duplicates is done quite simply using the static IndexOf method of the Array object. The current element of the Cards array is not filled and the array counter i isn't incremented if the number already exists in the array.
The Repeat method of the Enumerable object makes it very convenient to base the size of the array on a variable. Since I decided to do some testing using different array sizes, this was a requirement for me.
When I ran this code in a Windows form, I got this result for a standard 52 card deck.
Click Here to display the illustration
Dealing cards using this array would be easy. Assume a particular order of cards. (Spades, Hearts, Diamonds, Clubs would be 0 through 3 for example.) Since the first random integer is 48 in the illustration above, the first card can be found by first getting the integer part of 48 divided by 13 (48 \ 13) equals 3. The remainder is 9 (48 mod 13). So the first card is a 9 of Clubs.
The problem with this approach is that creating the last few elements of the array takes a lot of cycles because the random integer generator has to make a lot more guesses before it finds one that isn't duplicated. (The original version of this article had a bug in it. I used the BinarySearch static method of the Array object instead of the IndexOf method. Binary.Search didn't find duplicates, although it appeared to with just casual inspection. Sorry 'bout that.)
I ran a few tests to see just how much time the "find the duplicates" method does take as it searchs for the last few elements. This test with an array of 1000 elements shows that the amount of time increases linearly.
Click Here to display the illustration
But it's still a lot more than the other commonly used method that we discuss next. This method is not recommended, in spite of the fact that it's fast, because it doesn't create a really random distribution of the cards.
The code to shuffle the cards, the other major algorithm, is straightforward too.
Dim Cards() As Integer Dim Tmp As Integer Dim ReplaceLocation As Integer Dim i As Integer Dim Cards() = Enumerable.Repeat(0, theSize).ToArray() For i = 0 To theSize - 1 Cards(i) = i + 1 Next For i = 0 To theSize - 1 ReplaceLocation = Int(theSize * Rnd()) Tmp = Cards(i) Cards(i) = Cards(ReplaceLocation) Cards(ReplaceLocation) = Tmp Next
This requires two loops rather than one. The first to create an ordered array and the second to shuffle the ordered array. But there's no requirement to search the array while it's being created.
If all you're doing in your program is dealing one hand of poker, it's not worth worrying about. But there are much better methods and the next article in this series shows one to you. You can read it here.