Generate random numbers in a random fashion

Question

How can I generate 9 random numbers between 1 to 9,without repetition, one after another. Its like: Lets assume that the first random number generated is 4, then the next random number has to be in [1, 9] - {4}. My first approach was to add each randomly generated number to a set, and so avoid duplication. But then in worse cases, like we have already generated 6 and we have to generate 3 more numbers, the process goes a little slow. ANd when the range is changed from [1, 9] to [1, 1000], this approach doesn't sound correct. Can anyone suggest an alternative approach.

Answer 1

The Fisher-Yates Shuffle gives an efficient way of generating a permutation uniformly at random. From an initial list, it performs $O(n)$ swaps.

Afterwards, we can just read the entries from the permutation.

Answer 2

What you want is to find a permutation of the set $\{1,2,3,4,5,6,7,8,9\}$. There are $9!$ such permutations in general, and picking one at random will produce an ordering of the numbers.

The easiest way to do it is to have a way of selecting a random element from a set. That way, you just perform the process:

• Pick random number $x$ from $S$
• Replace $S$ with $S\setminus \{x\}$
• If $S$ is not empty, repeat first step.

Answer 3

First generate generate a random number 1 to 9; lets say you get 4

Next generate a random number 1 to 8 Lets say you get 5 so the number you use is the 5th one you have not already used so it would be 6.

Next generate a random number 1 to 7 Lets say you get 2 so the number you use is the 2nd one you have not already used so it would be 2.

Repeat for all numbers.

Answer 4

generate any number k
select number (k mod 10), enumerate the remaining 9 numbers in sequence
generate any number k
select number (k mod 9), enumerate the remaining 8 numbers in sequence
etc.