0
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ exactly what i was looking for...thanks $\endgroup$ – gonephishing Jul 1 '14 at 11:58
1
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ array based implementation of this algorithm will work...Thanks $\endgroup$ – gonephishing Jul 1 '14 at 11:57
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ yes...just got this algorithm link $\endgroup$ – gonephishing Jul 1 '14 at 11:59
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Velcome to the site! However, when answering questions, you should try to be more helpful, such as giving reasons for your answer, which you did'nt do here. $\endgroup$ – kjetil b halvorsen Jul 1 '14 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.