Readers Feedback

---

The Editors and Readers of COMPUTE!


Unique Random Numbers
I am writing a program that requires random numbers to control the game, but the problem is I want to filter out the random numbers that have already been picked. I'm using an Atari computer. What's the solution?

There are a couple of solutions to this problem, and they apply to nearly any version of BASIC. Which method is fastest and most efficient depends on the particular requirements of your program. You may be writing an arcade-style game which needs to position characters or objects randomly about the screen, each in a different location; or you may be writing a card game simulation that requires a "shuffled" pile of 52 random numbers.
    The most common approach is to generate a random number, check it against a list of previously generated random numbers stored in an array, and then generate a new number if there's a match. This can be done by a subroutine that your program calls whenever it needs a unique number. Here's an example in Atari BASIC that works with little or no modification in most other BASICS:

10 SIZE=100:DIM ARRAY(SIZ
   E):A=1
20 FOR J=1 TO SIZE:ARRAY(
   J)=0:NEXT J
30 GOSUB 1000:REM GET UNI
   QUE RANDOM NUMBER
40 PRINT "UNIQUE VALUE #"
   ;A-1;" = ";RNUM
50 IF A<SIZE+1 THEN 30
60 END
1000 RNUM=INT(RND(1)*1000
     +1)
1010 PRINT RNUM
1020 J=1
1030 IF RNUM=ARRAY(J) THE
     N 1000
1040 J=J+1:IF J<SIZE+1 TH
     EN 1030
1050 ARRAY(A)=RNUM:A=A+1:
     RETURN
    
    Line 10 defines the size of the array which stores the random numbers and sets A=1 as an index into the array. You can change the variable SIZE, of course, to create any size array you need. Line 20 clears out the array with zeroes. The statements in these two lines should be placed in the initialization section of your program, followed by your own code.
    Line 30 calls the random number subroutine, which begins at line 1000. The statement in line 1000 generates a random number (RNUM) between 1 and 1000 in Atari BASIC. Make whatever changes are appropriate for your particular program or version of BASIC. Line 1010 can be omitted in your own program-it simply prints the newly generated random number on the screen for this demonstration. Lines 1020-1040 set up a loop which compares RNUM to each element in the array. If a match is found-meaning the random number was previously generated and stored in the array-the program goes back to line 1000, which makes a new random number and repeats the process. If no match is found anywhere in the array-meaning the random number is unique-the program continues to line 1050. This line adds the number to the array, increments the array index (A=A+1), and finally ends the subroutine with a RETURN.
    (Incidentally, some of you may be wondering why we didn't use a FOR-NEXT statement for the loop in lines 1020-1040. We didn't because the IF-THEN statement in line 1030 frequently jumps out of the loop back to line 1000 whenever it finds a match, and this could eventually cause a stack overflow and out-of-memory error.)
    Lines 40 and 50 can be omitted from your own program. They merely print the random numbers on the screen for this demonstration.
    This method of generating unique random numbers works, but suffers from a few problems. For one thing, if you need a great many random numbers, or if you can't predict how many you'll need as your program runs, your computer may not have enough memory for the large array that's required. Also, if the number of random numbers you need coincides with the allowable range of the random numbers, this routine slows down almost to a crawl as it struggles to generate the last few unique numbers.
    An example of the latter problem is when you're programming a card game simulation and need a randomized list of 52 unique numbers from 1 to 52, each number representing a card. To see a demonstration, set SIZE=52 in line 10 and modify line 1000 so it generates random numbers restricted to the range of 1-52. When you run the program, at first it has no trouble coming up with unique numbers. But soon it begins exhausting the possibilities. By the time it reaches the forty-fifth unique number, it is having real trouble generating numbers which haven't been made before. The fifty-second number is the hardest of all-it might take a minute or longer. (There are better ways to shuffle a list of numbers for card games, but we haven't room to cover them here.)
    If repeated calls to this subroutine slow down your program too drastically, rewrite it slightly to fill the array with all the unique numbers your program will need. Then call the routine just once, as your program initializes. Later, whenever your program needs a unique random number, it can simply pull a number out of the array, incrementing a counter each time so the same number isn't retrieved more than once.