0
$\begingroup$

Algorithms like Knuth's algorithm or this one, works for a range that is known in advance(like shuffling numbers 1 to 11), in this case the range will never change. You'll always get a random no. between 1 to 11.

But in my case the range can increase like if the generator generates 2 random numbers {3,5} from the range 1 to 11, and then the range becomes 1 to 13, the next random number should be from this new range but shouldn't repeat 3 or 5.

Is it possible without making a large record of every used number and then iterating to find out if it is unique or not.

Edit:

If I have to find a random number between 1 and 11 I can easily shuffle these numbers and pick them by index 0,1,2,... and I'll get non-repeating pseudo random numbers. But after picking 3 index from the list that can be 3,5,4 and after this, the algorithm have to find random numbers between 1 and 13.

Now If I reshuffle the new list that contains numbers 1 to 13. There is no guarantee that the generated numbers will not repeat. and if I simply append these 2 numbers (12,13) to the shuffled list of numbers 1 to 11, they are not random.

Is there a way to still get the pseudo random numbers without repetition?

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! It's hard for me to understand exactly what problem you're trying to solve and what you're trying to achieve. Can you describe the distribution on outputs you want your algorithm to have? Can you provide a clearer description of the approach you have in mind (e.g., concise pseudocode)? $\endgroup$ – D.W. Jun 2 '17 at 19:13
  • $\begingroup$ I'm still not quite sure what the scenario is. Suppose that you're trying to generate non-repeating numbers in the range 1-10 and you happen to pick 1, 2, 3. Then, suppose the range is changed to 1-3. Now what? It's impossible to pick anything without a repetition. $\endgroup$ – David Richerby Jun 3 '17 at 12:46
  • $\begingroup$ @DavidRicherby It'll not generate any number if the number of already generated numbers is greater than the size of range. $\endgroup$ – Anubhav Jun 3 '17 at 13:17
  • $\begingroup$ @anubhavyadav: Careful. Range 1-10, I pick 1, 5, 8, 9, change the range to 1-3. Easy to get two more numbers. $\endgroup$ – gnasher729 Jun 4 '17 at 14:07

Your Answer

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

Browse other questions tagged or ask your own question.