Generate random numbers without repeats

Question

I want to generate random numbers without repeats till all gone, then again generating random numbers with the initial dataset.

I know keeping already generated numbers in an array and loopin through them to check whether it is alredy generated or the method deducting the numbers that are generated from the array and randomize numbers with the new array.

What I want is not those methods, if there is a way that is efficient using data structures will be quite nice, if it is any other method also ok

Thanks

It doesn't matter what the language is I just want an algorithm or method of doing that — Dilini Himali, Feb 17 '15 at 06:19
possible duplicate of [Most efficient way of randomly choosing a set of distinct integers](http://stackoverflow.com/questions/3722430/most-efficient-way-of-randomly-choosing-a-set-of-distinct-integers) — pjs, Feb 17 '15 at 14:58

score 0 · Answer 1 · answered Feb 17 '15 at 05:01

I'm not sure what language you are using, but here's some C++ code that does what you're looking for. Instead of it searching an array, it just does a direct check of a specific section of memory for a set flag and if it isn't set then the number chosen is new and printed.

The section I marked as handler is the code that is first executed when a unique number is found. Change the 10's and the 11 to different numbers if you want a larger set of random numbers but you might have to wait forever for the output.

int main(int argc, char *argv[]){
char randn[10];
char randnset[10];
int n;
int ct=0;
memset(randnset,'1',10);
memset(randn,0,10);
while (ct < 10){
    srand(time(NULL));
    n=rand() % 11;
    if (!randn[n]){
        printf("%d\n",n); // handler
        randn[n]='1';
        ct++;
    }
}
return 0;
}

score 0 · Answer 2 · answered Feb 17 '15 at 05:07

Every random generator function takes a seed value as a parameter and uses it in its internal algorithm to generate random numbers. If you want to generate the same sequence of numbers, you have to use the same seed value. As an example you can achieve this in Java like this:

int seed = 10;
Random r = new Random(seed);
for(int i=0; i<10; i++){
    System.out.println(r.nextInt());
}

The output is something like this (of course it will have different results in your system):

-1157793070
1913984760
1107254586
1773446580
254270492
-1408064384
1048475594
1581279777
-778209333
1532292428

and it gives me the same results each time I execute it.

What I need is not the same sequence to appear again and again, what I need is when all the numbers are generated then randomize the initial numbers again and in a particular sequence a number shouldn't be repeated, Thanks — Dilini Himali, Feb 17 '15 at 06:16

score 0 · Accepted Answer · answered Feb 17 '15 at 14:26

Say you want to generate 1,000 unique random numbers and present them to some code one at a time. When you exhaust those numbers, you want to present the same numbers again, but in a different sequence.

To generate the numbers, use a hash table. In C#, it would look like this:

const int MaxNumbers = 1000;
HashSet<int> uniqueNumbers = new HashSet<int>();
Random rnd = new Random();
// generate random numbers until there are 1000 in the hash table
while (uniqueNumbers.Count < MaxNumbers)
{
    uniqueNumbers.Add(rnd.Next());
}
// At this point you have 1,000 unique random numbers
// Put them in an array
int[] myNumbers = uniqueNumbers.ToArray();

This works because the HashSet.Add method rejects duplicates. And it's very fast because lookup in the hash table is O(1).

Now, you can serve them by setting a current index at 0 and increment it every time a number is requested. Something like:

int ixCurrent = 0;
int GetNextNumber()
{
    if (ixCurrent < MaxNumbers)
    {
        ++ixCurrent;
        return myNumbers[ixCurrent-1];
    }

But what to do when ixCurrent runs off the end of the array? Enter the Fisher-Yates Shuffle:

    // out of numbers. Shuffle the array and return the first one.
    for (int i = MaxNumbers-1; i > 0; --i)
    {
        int j = rnd.Next(i+1);
        int temp = myNumbers[i];
        myNumbers[i] = myNumbers[j];
        myNumbers[j] = temp;
    }
    ixCurrent = 1;
    return myNumbers[0];
}

If you know that the numbers you want to return are within a particular range (that is, you want to return the numbers 0-999 in random order), then you just fill an array with the values 0-999 and shuffle it.

Generate random numbers without repeats

3 Answers3