Select & discard algorithm for unique random numbersMarch 23 2008 at 1:16 AM
|Solitaire (Login Solitaire1)|
Response to Shuffle Sort algorithm - unique random numbers with no duplicates
Put the numbers into a hat, mix them up, and pull them out one by one (without looking), discarding each used number.
There are various algorithms for implementing such a scenario. Most involve use of an array. The following techniques are for creating a set of unique random selections from a range without duplicates:
1- One way is a random mix (reordering) of the array indexes and selecting the numbers in order of the rearranged array index. This code is shown in the above post.
2- Another is to test with each new selection whether that selection was among the discards and trying again. This can get very inefficient if you start with a large number and come down to the last few numbers. This technique discards used numbers, makes a random selection from among all the numbers in the range again, and tests the used numbers before keeping the selection.
3- Yet another way might be to make a random selection anywhere within an array of sequential numbers (like pulling numbers out of a hat), then removing that value from the array and moving down all the remaining values past that index to eliminate the gap. The last array index would then be emptied and eliminated by decrementing the range with each new selection. This technique is the opposite of #2 -- it discards used numbers and makes new selections from the remaining unused numbers until only one is left.
I decided to come up with code to implement the third method, which I don't believe has been done before.
This program simulates the action of pulling sequentially numbered tickets randomly out of a hat. The result is a set of unsorted unique numbers without duplicates within the range.
My usual technique is to use the shuffle sort algorithm, which is the most efficient. Some people use the least efficient method of testing the discards to make sure it doesn't duplicate any of the selected numbers. This algorithm is the opposite. It discards selected numbers and picks a new number from the ones remaining. It works by selecting a random index which will contain the selected number in the array, then moves the array values down to overwrite the selected index, and decreases the range with each repeat.
This version of the program allows repeats of a user-defined range, and also allows a new range to be defined, using three nested DO loops. Here is the code:
'Set of unique random numbers in a range without duplicates
'Simulate pulling number out of a hat; remove selected number from mix
DIM range AS INTEGER, ran AS INTEGER, x AS INTEGER
DIM index AS INTEGER, rng AS STRING, ans AS STRING
PRINT "Press any key to repeat, Tab for a new range; Esc to quit..."
INPUT "Enter a range up to 22: ", rng$
ran = CINT(VAL(rng$))
IF ran > 20 THEN ran = 22
IF ran < 2 THEN ran = 2
REDIM arry(ran) AS INTEGER
range = ran
FOR x = 1 TO range 'assign sequential values to array
arry(x) = x
index = INT(RND * range + 1) 'select random index
PRINT arry(index); 'selected number
'discard arry(index); move array down to overwrite selected index
FOR x = index TO range - 1
arry(x) = arry(x + 1)
range = range - 1 'decrease array range after discard
LOOP UNTIL range = 0 'no more numbers in hat
PRINT : PRINT
ans$ = INPUT$(1)
LOOP UNTIL ans$ = CHR$(27) OR ans$ = CHR$(9)
LOOP UNTIL ans$ = CHR$(27)