A Sample Of Brilliance
Contents
I recently read a paper called “A Sample of Brilliance” by Jon Bentley
– it was published for September 1987 column of Programming Pearls. The
column deals with generating random sequences if we are already given an
random integer generating function (called RandInt(i, j)
).
The column is small and advanced, and starts with the following implementation:


While this looks like a great implementation, it kind of goes impossible
when m = n
, and the number is large. In such case, as the algorithm is
finding the last few elements, the chances of every random element being
inside the set are very high resulting in nontermination of the loop in
some cases.
Floyd suggested a very nice approach: never include the last element of the range and include it only if the random generated value is repeated in the set:


The insight is that the set will always some numbers, and each new iteration is going to increase the range of numbers by 1. At any such iteration, if the random number generated is already in the set, just include the new range’s last number, which is guaranteed to be not present in the set as of the current iteration.
Based on this knowledge, we can also generate a random sequence instead of set:


Author Tushar Tyagi
LastMod Feb 9, 2018