264 APPENDIX B
each random number generated. This reduces the chance of two locations
having sequential numbers, because that will only happen when the adjacent
location is free and the number generated mod the number of spaces still free
results in 1.
The algorithm to accomplish this is
for i = 1 to N do
theList[i] = 0
end for
location = 1
freeCount = N
for i = 1 to N do
skip = freeCount*RanNum() + 1
while skip > 0 do
location = (location mod N) + 1
if theList[location] = 0 then
skip = skip - 1
end if
end while
theList[location] = i
freeCount = freeCount - 1
end for
In this algorithm, we use how many cells are free, and generate a random
number up to that value. This is done so that we don’t have to loop though the
list more than one time. You should see that the while loop will always end,
because even in the last case, there will be at least one empty location.B.3 SUMMARY
This appendix gives one technique that can be used in a program to gener-
ate pseudorandom numbers and then shows how that can be used to create a
random list of values. These methods could be used to create lists that can then
be searched or sorted to measure the complexity of various algorithms from
Chapters 2 and 3.