RPL: Random Numbers without Duplicates

[Joe Horn]

In the Good Old Days, Richard Nelson and I taught an HP 48 Programming Class every Friday evening at EduCALC for many years. We often prepared and presented a paper on some particular programming concept. Here's one that I wrote and presented, which may be of interest to new HP 48/49/50 owners. -jkh-

Random Numbers without Duplicates
(aka Selection without Replacement)
for RPL Calculators
by Joseph K. Horn

When you’re winning at craps, it is tempting to believe that the dice are “hot”, causing a “winning streak”. Professional gamblers all seem to believe this, because they bet higher than normal during what they perceive as “winning streaks”. But it’s all superstitious nonsense, of course. The probability of the dice winning is always the same, regardless of previous rolls. “Dice have no memory,” says the old adage, and it’s obviously true, no matter what the gamblers say.

Therefore, to imitate dice throws on the HP 48, it is sufficient to generate random numbers between 1 and 6 without keeping any record whatsoever of previous “throws”.

Here’s a simple program that throws one die:

Code:

'DIE'
« RAND 6 * CEIL »

Throwing dice is therefore exactly like pulling a random number (1 through 6) out of a hat, and then putting the number back into the hat. The next throw (or number pulled out of the hat) can be any number, including the number thrown (pulled out the hat) last time. This is called “selection with replacement” because we are randomly selecting an item from a collection and then putting it back into the collection so that it can be selected again.

Therefore several dice can be thrown by running ‘DIE’ more than once. A program that throws two dice is this simple:

Code:

'DICE'
« DIE DIE 2 →LIST »

By changing the 6 in the ‘DIE’ program to a 2, you’d turn it into a ‘COINFLIP’ program that generates either a 1 (head) or a 2 (tail). Likewise, changing the 6 to a 52 would create a ‘DEAL’ program that generates a random number between 1 and 52, which could be used to model a random card from a standard poker deck:

Code:

'DEAL'
« RAND 52 * CEIL »

But here we see a problem arise. Unlike the ‘DICE’ program, which relies on the fact that dice have no memory, the ‘DEAL program cannot be run more than once to imitate dealing more than one card. When dealing cards from a deck, the deck does “remember” which cards have been dealt, because they are gone from the deck, and cannot be dealt again. The ‘DEAL program, however, does not know this, and can deal the same card twice. The following ‘DEAL5’ program seems like it ought to deal five cards, and in fact it usually does; but once in a while, it deals “repeats”. This would be like having two aces of the same suit... an event that inevitably leads to a barroom brawl in western movies.

Code:

'DEAL5' (don’t use!)
« 1 5 START DEAL NEXT 5 →LIST »

So we have to find some way of “remembering” the cards that have been dealt so far, and not deal them again. This is called “selection without replacement”, because it’s like selecting an item from a collection, and not putting it back into the collection, so that it cannot be selected again.

One way is to keep all the cards dealt so far in a list, and then when a random card is generated, search the list to insure that it isn’t in the list. If it’s not in the list, then deal it (add it to the list); but if it’s already in the list, generate another random card. This is a good and fast method when the number of cards to be dealt is small, but gets very slow when dealing many cards. As the size of the list of already-dealt cards increases, it gets less and less likely that a randomly generated card is not in the list. Dealing the entire deck can take a long time, as the last few cards are found by trial and error.

The following program, ‘DEAL1’ (Deal, method 1), picks X random numbers between 1 and Y, without repeats. It uses the “search the list and try again” method described above.

Code:

'DEAL1'
« { } 1 ROT
  START
    WHILE OVER RAND * CEIL DUP2 POS
    REPEAT DROP
    END +
  NEXT SWAP DROP
»

If very many random numbers are to be generated, ‘DEAL1’ bogs down. Another method of “selection without replacement” can be used. This alternate method actually creates all the numbers between 1 and Y, randomly placing them all on the stack (like shuffling the whole deck of cards), then drops all but X of them. Although this sounds complicated, the RPL code is surprisingly simple, fast, and elegant. The following ‘DEAL2’ program (Deal, method 2), like ‘DEAL1’, picks X random numbers between 1 and Y, without repeats. It uses the “shuffle and discard the rest of the deck” method described above.

Code:

'DEAL2'
« → t n
  « 1 t
    FOR x x DUP RAND * CEIL ROLLD
    NEXT t n - DROPN n →LIST
  »
»

It is interesting to study which program is faster for which inputs. Note well that ‘DEAL2’ always takes the same amount of time to finish, regardless of X, whereas the execution time of ‘DEAL1’ grows exponentially as X approaches Y, and due to its algorithm, can take different amounts of time even with the same inputs. It is even possible for ‘DEAL1’ never to terminate... but highly improbable.