Suppose you want to make a random 9 digit number, using every number from 1 to 9 exactly once. You have a process called random(top) that gives a random number up to top (if top was 5, it would give random numbers from 1 to 5)

a) How could you do this?

b) If top couldn't be more than 9, how could you do this using random(top) only 9 times (or less)?

a) Suppose we have a 9 digit number, each digit being unique.  Break it down into possibilities.  Given such a restraint, we can assume there are only 9! such numbers (362880).  Now we only need to call random(362880) and use the generated random number as the encoded version of the number.  We can easily develop an algorithm that generates a list of all such 362880 combonations of digits, and pick the N'th one, where N is some random number between 1 and 362880.

b) Use part A, but instead of using random(362880), we can use random(9)-1 to generate a number, multiply it by 9, add random(9)-1 again, multiply by 9 again, and repeat 6 times until we have a integer in the range of 0-531440.  With such an integer, we can surely break it down to a number between 1 and 362880.  This again generates the N'th element of an array of all possible numbers meeting the criteria, but in only 6 calls to random(top)

Note: The process of breaking down a larger integer into a smaller integer can be done in a number of ways, but the resulting random sequence of digits is weighted towards certain numbers more than others.

Posted by paul on 2005-12-13 18:09:19