The redoubtable Welopez attacked a problem in issue #12 to prevent getting duplicate cards (or duplicate anything) when selecting at random. His approach was to generate repeatedly a random number, and then add it on the end of an array, but first check that it did not already exist in the array. In the example he was “drawing” a poker hand from a deck of 25 cards.
He admitted a few problems: the more often you draw a card, the more likely it will be a duplicate already in the array – so it would be rejected and a new random drawing would have to take place. At computer speeds this will rarely cause problems, but the larger the selection from which the draw is made, the longer his routine is likely to take.
There is a way to avoid all this, yet still ensure that selecting a card at random will not involve any comparisons to avoid duplications! As a matter of fact, the method I share here works at blistering speed to “shuffle” the elements of an array of ANY size: then you need only draw cards one by one from the top of the deck (or in programming terms, sequentially from the array).
In this example I will shuffle a deck of 52 cards. The items you want to shuffle can be in an array of their own – perhaps a string array of 52 entries, one of which is “Ace of Spades”, and so on. But this array will not change at all: so instead of a DIM, your array can even be individual records in a disk file. You may ask, “how can we shuffle, then?” The secret is that we will have another array, a DIM with the appropriate number of entries. First of all we initialize it so that each entry is just a sequential number:
DIM Deck(52)
FOR i = 1 to 52
Deck(i) = i
NEXT
Suppose we select any one of these entries (using RND of course) and exchange it with the first entry (representing the “top card”). Just BASIC has no SWAP command, but it is still very easy to swap them. This, in effect, has selected a random card to become the TOP card in the deck -- not the card itself, but its sequence number between 1 and 52. It still works if you try to swap a card with itself. Note that the way to get a random number between 1 and N is:
1 + INT(RND(0) * N)
This is because RND(0) returns a positive number less than one. Multiplying by N, you get a positive number less than N. The integer part of this will be a whole number between 0 and (N-1), so we just add one to make it a number between 1 and N. You can make an easy change to get any range of whole numbers: if you want a random whole number between 5 and N, you simply add four to a randomly-chosen number between 1 and (N-4).
This is:
4 + (1 + INT(RND(0) * (N – 4))
or, in general, for a random whole number between X and N (moving the odd “1” around a little):
X + INT(RND(0) * (N – X + 1))
Back to our deck of 52: randomizing the first card is done by:
a = 1 + INT(RND(0) * 52) b = Deck(1) Deck(1) = Deck(a) Deck(a) = b
We want to do this for all fifty-two cards at once, and this calls for changes to put it inside a loop:
FOR i = 1 to 51
a = i + INT(RND(0) * (53 – i)
b = Deck(i)
Deck(i) = Deck(a)
Deck(a) = b
NEXT
Note that we don’t need to randomize the last card (namely Deck(52)): our shuffle is finished when we have done 51 turns of the loop. Shuffling always takes the same amount of time – and yet there are no “compares” needed to prevent drawing duplicates. Even better, it works for any size array, and doubling the size of the array only doubles the time taken to shuffle (which isn’t so with Weloped’s routine, though his routine is satisfactory for very small arrays). Welopez put together his code as a program that was able to randomize 25 cards in well under 100 milliseconds. I built several different program versions using his code randomizing different quantities of cards; I also built these same programs, substituting the new code. After running each program ten times I established for each decksize the average time taken to shuffle and the nimber of times each had to “visit” the time-consuming randomize function. Here are the results:
Decksize OLD: time visits NEW: time visits
-------- --------- ------ --------- ------
25 34.4 ms 121.6 15.4 ms 25
52 87.4 ms 223.8 15.6 ms 52
312 3473.0 ms 1379.8 15.8 ms 312
1024 44996.8 ms 7357.0 47.0 ms 1024
Yes, that’s right: sorting an array of about a thousand entries the old way takes the better part of a minute – but the new still takes only a tiny fraction of a second! It’s hard to believe how much better the new code’s performance is: yet you can confirm it for yourself, inspecting the code for fairness and accuracy. In the supplement to this article, these test programs are oldShuffleXXX.bas and newShuffleXXX.bas, where XXX is replaced in turn by 25, 52, 312 and 1024.
As an aside you might like to see a method of converting the numbers 1 to 52 into actual playing card ranks and suits. This is about the easiest way
I’ve found:
FUNCTION Card$(num)
Suits$ = “Spades Hearts Diamonds Clubs”
Ranks$ = “Ace 2 3 4 5 6 7 8 9 10 Jack Queen King”
a = (num-1) MOD 13 + 1
b = INT((num-1) /13) + 1
Card$ = WORD$(Ranks$, a);” of “;WORD$(Suits$, b)
END FUNCTION
This works very nicely indeed. If you feel a bit “retro” you can modify Ranks$ to have Deuce and Trey instead of 2 and 3. This function is inserted into newShuffle52 where you can give it a test drive.
Remember: it expects only numbers between 1 and 52.
Okay... I'm a senior citizen, and sometimes thick-headed, which may be a result of bumping my head too many times when I was a paratrooper in the US Army. It took me quite awhile to figure out "why" Wilf's code worked without repeating any value previously used.
Fifty-two cards were too many for me to visualize, so I wrote a short snippet to choose one of 10 numbered balls, like KENO or BINGO. Code for a simple demonstration:
'Select one of 10 balls
'Demo by Welopez, based on code from Wilf Hey
choices=10 'the number of balls we have to choose from
DIM ball(choices) 'an array to hold all 10 balls
FOR k=1 to choices
ball(k)=k 'Fills the pigeon-holes with consecutive numbers
NEXT k
begin=TIME$("milliseconds") 'begin timing the shuffle
FOR k=1 TO choices
'Slight of hand
num = k+INT(RND(0)*(choices-k+1)) 'values less than k are not available
x=ball(k) 'selects the ball from current pigeon-hole
ball(k)=ball(num) 'put the random value into slot
ball(num)=x 'swap current ball with ball from current pigeon-hole
'End of slight of hand!!
NEXT k
finish=TIME$("milliseconds") 'stop timing, the balls have been shuffled
'===== Display the results
FOR k=1 to choices
PRINT TAB (n); ball(k); 'show the random choice of balls
n=n+5 'formats the column position
IF n=65 THEN
PRINT 'insert a blank line after each 13 numbers
n=0 'reset the column counter
END IF
NEXT k
PRINT: PRINT "The deck was shuffled in "; finish-begin; " milliseconds."
END
The code above is very simple, but the program employs a bit of slight of hand to insure that no choice is repeated. The action is the same as if we dumped all the balls into a black-bag, then drew them out one at a time. It's easier for me to visualize our "deck" as an old-fashioned desk with 10 pigeon-holes for numbered balls. The first loop fills each pigeon-hole sequentially, with numbered balls from 1 to 10. The slight of hand, when dealing, is in these few lines:
FOR k=1 TO choices
'Slight of hand, swap the balls!!
num = k+INT(RND(0)*(choices-k+1)) 'values less than k are not available
x=ball(k) 'selects the value from current pigeon-hole
ball(k)=ball(num) 'put the random value into pigeon-hole
ball(num)=x 'swap current num with ball removed from pigeon-hole
'End of slight of hand!!
NEXT k
We begin with 10 possible choices. In the first iteration k=1; we add a random number to k, between 0 and 1, times the number of possible choices minus k, plus 1. k is the first pigeon-hole in the desk, plus a random value times a value from the remaining 9 pigeon-holes, plus 1 to insure we have an integer value of at least 1.
x is the ball currently in pigeon-hole k, ball(k). We swap the ball currently in the pigeon-hole with a random numbered ball, ball(num). Then ball(num) assumes the value of the ball removed from the pigeon-hole and is placed in one of the pigeon-holes not yet visited. We repeat the process for all 10 pigeon-holes.
Even if our random number generator selects the same pigeon-hole for the next iteration, the ball in that pigeon-hole has a new value, ball(num)=x. Try modifying the line to choose a random number as follows:
num = 6 'Always get the value from pigeon-hole number 6 (or any one of 10 choices
Step through the program line by line. With the first iteration, pigeon-hole 1 becomes ball(num), and pigeon-hole 6 (ball(k)) gets the ball removed from pigeon-hole 1. In the second iteration, pigeon-hole 2 becomes ball(num) and pigeon-hole 6 becomes ball(k). The results for succeeding iterations are identical, except pigeon-hole 6 will have a different value every time we visit it, until all 10 balls have been chosen. Eventually, pigeon-hole 6 becomes 10 because that is the last number remaining, num=k+INT(RND(0)*(choices-k+1)), where k=10 and choices-k=0, plus 1. Because we remove each pigeon-hole from consideration with each iteration, we cannot possibly repeat a number. How slick is this?
I set up the print routine to display a maximum of 13 cards per line. You can change the value of choices to any multiple of 52 (104, 156, 208, 260, etc.) to simulate playing with multiple decks. You will always get 13 values per line, with no repeats anywhere in the output.
Determining Rank and Suit For a Deck of Fifty-Two Cards
FOR k = 1 to Decksize
PRINT Card$(deck(k)) 'Get rank and suit from FUNCTION Card$()
NEXT k
FUNCTION Card$(num)
Suits$ = "Spades Hearts Diamonds Clubs"
Ranks$ = "Ace 2 3 4 5 6 7 8 9 10 Jack Queen King"
a = (num-1) MOD 13 + 1
b = INT((num-1)/13) + 1
Card$ = WORD$(Ranks$, a);" of ";WORD$(Suits$, b)
END FUNCTION
There are 52 (or a multiple of 52) cards in array deck(). The FUNCTION makes use of the MOD function in Just Basic. a is the value of array deck(k), divided MOD 13, plus 1. We cannot use a remainder of 0 if we divide 13, 26, 39, etc, so we add 1 to get the next WORD$(Ranks$,a). We use the same trick to set b = INT((num-1)/13)+1 to get WORD$(Suits$,b). No matter how many cards are in our deck, cards 1-13 will be Spades, 14-26 will be Hearts, 27-39 will be Diamonds, and 40-52 will be Clubs. The INT value of (num-1), divided by 13 and adding one to insure we have a whole number, will calculate b for use in WORD$(Suit$, b). Now you have learned another "slick trick."