How to make Random Numbers unique

Question

I am making a random number generator. It asks how many digits the user wants to be in the number. for example it they enter 2 it will generate random numbers between 10 and 99. I have made the generator but my issue is that the numbers are not unique.

Here is my code. I am not sure why it is not generating unique number. I thought srand(time(null)) would do it.

void TargetGen::randomNumberGen()
{
srand (time(NULL));
if (intLength == 1)
{

    for (int i = 0; i< intQuantity; i++)
    {
        int min = 1;
        int max = 9;
        int number1 = rand();

        if (intQuantity > max)
        {
            intQuantity = max;
        }

        cout << number1 % max + min << "\t";

    }

}
else if (intLength == 2)
{
    for (int i = 0; i<intQuantity; i++)
    {
        int min = 10;
        int max = 90;
        int number1 = rand();

        if (intQuantity > max)
        {
            intQuantity = max;
        }

        cout << number1 % max + min << "\t";


    }

}

if (intLength == 3)
{
    for (int i = 0; i<intQuantity; i++)
    {
        int min = 100;
        int max = 900;
        int number1 = rand();

        if (intQuantity > max)
        {
            intQuantity = max;
        }

        cout << number1 % max + min << "\t";
    }

}
else if (intLength == 4)
{
    for (int i = 0; i<intQuantity; i++)
    {
        int min = 1000;
        int max = 9000;
        int number1 = rand();

        if (intQuantity > max)
        {
            intQuantity = max;
        }

        cout << number1 % max + min << "\t";
    }

}

if (intLength == 5)
{
    for (int i = 0; i<intQuantity; i++)
    {
        int min = 10000;
        int max = 90000;
        int number1 = rand();

        if (intQuantity > max)
        {
            intQuantity = max;
        }

        cout << number1 % max + min << "\t";
    }

}
else if (intLength == 6)
{

    for (int i = 0; i<intQuantity; i++)
    {
        int min = 100000;
        int max = 900000;
        int number1 = rand();

        if (intQuantity > max)
        {
            intQuantity = max;
        }

        cout << number1 % max + min << "\t";


    }

}

if (intLength == 7)
{
    for (int i = 0; i<intQuantity; i++)
    {
        int min = 1000000;
        int max = 9000000;
        int number1 = rand();

        if (intQuantity > max)
        {
            intQuantity = max;
        }

        cout << number1 % max + min << "\t";
    }

}
else if (intLength == 8)
{
    for (int i = 0; i <intQuantity; i++)
    {
        int min = 10000000;
        int max = 89999999;
        int number1 = rand();

        if (intQuantity > max)
        {
            intQuantity = max;
        }

        cout << number1 % max + min << "\t";
    }

}

if (intLength == 9)
{
    for (int i = 0; i < intQuantity; i++)
    {
        int min = 100000000;
        int max = 900000000;
        int number1 = rand();

        if (intQuantity > max)
        {
            intQuantity = max;
        }

        cout << number1 % max + min << "\t";
    }

}
}

Okay so I thought I figured out a way to do this without arrays but It isn't working before I switch to the fisher yates method. Can someone tell me why this isn't working? It is supposed to essentially take the random number put that into variable numGen. Then in variable b = to numgen. Just to hold what numGen used to be so when the loop goes through and generates another random number it will compare it to what the old number is and if it is not equal to it, then it will output it. If it is equal to the old number than rather than outputting it, it will deincrement i so that it will run through the loop without skipping over the number entirely. However, when I do this is infinitely loops. And I am not sure why.

if (intLength == 1) {

    for (int i = 0; i< intQuantity; ++i)
    {

        int min = 1;
        int max = 9;
        int number1 = rand();
        int numGen = number1 % max + min;


        if (intQuantity > max)
        {
            intQuantity = max;
        }

        for (int k = 0; k < 1; k++)
        {
            cout << numGen << "\t";
            int b = numGen;
        }
        int b = numGen;
        if (b != numGen )
        {
            cout << numGen << "\t";
        }
        else
        {
            i--;
        }

    }

}

How many numbers do you want? E.g., you cannot get 200 unique numbers between 10 and 99. — Paul Draper, Apr 13 '14 at 23:37
I thought srand(time(NULL)) would make it not repeat them just by nature. I am now thinking ill have to input the integers it makes into a array then compare them. But I am not sure how I will implement that yet. — user3530147, Apr 13 '14 at 23:39
You'll probably get a bit closer with ``, but no, they don't produce unique numbers every time. — chris, Apr 13 '14 at 23:39
I also get input from the user as to how many numbers they want. but I have a checker that will see if the user inputed a number more then the max then it will default it to what the max amount of numbers that range has in it. — user3530147, Apr 13 '14 at 23:40
There are no quality promises for `rand()`, so it can be quite shoddy. — Deduplicator, Apr 13 '14 at 23:40
Please: `int min=1; int max=9; for (int i = 1; i < intLength; i++) { min *= 10; max *= 10; }` — fejese, Apr 13 '14 at 23:42
You do realize that 'unique random' is a contradiction in terms? — user207421, Apr 13 '14 at 23:44

score 2 · Answer 1 · answered Apr 13 '14 at 23:55

Everyone has interesting expectations for random numbers -- apparently, you expect random numbers to be unique! If you use any good random number generator, your random numbers will never be guaranteed to be unique.

To make this most obvious, if you wanted to generate random numbers in the range [1, 2], and you were to generate two numbers, you would (normally expect to) get one of the following four possibilities with equal probability:

1, 2
2, 1
1, 1
2, 2

It does not make sense to ask a good random number generator to generate the first two, but not the last two.

Now, take a second to think what to expect if you asked to generate three numbers in the same range... 1, 2, then what??

Uniqueness, therefore, is not, and will not be a property of a random number generator.

Your specific problem may require uniqueness, though. In this case, you need to do some additional work to ensure uniqueness.

One way is to keep a tab on which numbers are already picked. You can keep them in a set, and re-pick if you get one you got earlier. However, this is effective only if you pick a small set of numbers compared to your range; if you pick most of the range, the end of the process gets ineffective.

If the number count you are going to pick corresponds to most of the range, then using an array of the range, and the using a good shuffling algorithm to shuffle the numbers around is a better solution. (The Fisher-Yates shuffle should do the trick.)

score 2 · Answer 2 · 2014-04-15T02:34:47.553

Hint 0: Use Quadratic residue from number theory; an integer q is called a quadratic residue modulo p if it is congruent to a perfect square modulo p; i.e., if there exists an integer x such that:

x² ≡ q (mod p)

Hint 1: Theorem: Assuming p is a prime number, the quadratic residue of x is unique as long as 2x < p. For example:

0² ≡ 0 (mod 13)

1² ≡ 1 (mod 13)

2² ≡ 4 (mod 13)

3² ≡ 9 (mod 13)

4² ≡ 3 (mod 13)

5² ≡ 12 (mod 13)

6² ≡ 10 (mod 13)

Hint 2: Theorem: Assuming p is a prime number such that p ≡ 3 (mod 4), not only x²%p (i.e the quadratic residue) is unique for 2x < p but p - x²%p is also unique for 2x>p. For example:

0²%11 = 0

1²%11 = 1

2²%11 = 4

3²%11 = 9

4²%11 = 5

5²%11 = 3

11 - 6²%11 = 8

11 - 7²%11 = 6

11 - 8²%11 = 2

11 - 9²%11 = 7

11 - 10²%11 = 10

Thus, this method provides us with a perfect 1-to-1 permutation on the integers less than p, where p can be any prime such that p ≡ 3 (mod 4).

Hint 3:

unsigned int UniqueRandomMapping(unsigned int x)
{
    const unsigned int p = 11; //any prime number satisfying p ≡ 3 (mod 4)
    unsigned int r = ((unsigned long long) x * x) % p;
    if (x <= p / 2) return r;
    else return p - r;
}

I didn't worry about the bad input numbers (e.g. out of the range).

Remarks

For 32-bit integers, you may choose the largest prime number such that p ≡ 3 (mod 4) which is less than 2³² which is 4294967291.
Even though, this method gives you a 1-to-1 mapping for generating random number, it suffers from the clustering issue.
To improve the randomness of the aforementioned method, combine it with other unique random mapping methods such as XOR operator.

score 1 · Answer 3 · edited May 23 '17 at 11:43

I'll assume you can come up with a way to figure out how many numbers you want to use. It's pretty simple, since a user input of 2 goes to 10-99, 3 is 100-999, etc.

If you want to come up with your own implementation of unique, randomly generated numbers, check out these links.

http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Here is a very similar implementation: https://stackoverflow.com/a/196065/2142219

In essence, you're creating an array of X integers, all set to the value of their index. You randomly select an index between 0 and MAX, taking the value at this index and swapping it with the max value. MAX is then decremented by 1 and you can repeat it by randomly selecting an index between 0 and MAX - 1.

This gives you a random array of 0-999 integers with no duplicates.

score 0 · Answer 4 · answered Apr 13 '14 at 23:39

0

Here are two possible approaches to generating unique random numbers in a range.

Keep track of which numbers you have already generated using std::set, and throw away and regenerate numbers as long as they are already in the set. This approach is not recommended if you want to generate a large number of random numbers, due to the birthday paradox.
Generate all numbers in your given range, take a random permutation of them, and output however many the user wants.

answered Apr 13 '14 at 23:39

merlin2011

71,677
44
195
329

Efficiency decreases fast: Birthday Paradox – Deduplicator Apr 13 '14 at 23:41
@Deduplicator, Agreed, it depends on how many he wants to generate though. That's why I suggested both, but I will update to make it mor eexplicit. – merlin2011 Apr 13 '14 at 23:42

score 0 · Answer 5 · answered Apr 13 '14 at 23:40

Standard random generators would never generate unique numbers, in this case they would Not be independent.

To generate unique numbers you have to:

Save all number generated and compare new one with old ones, if there is coincidence - regenerate.

or

Use random_shuffle function: http://en.cppreference.com/w/cpp/algorithm/random_shuffle to get all sequence in advance.

Tony Delroy · Answer 6 · 2014-04-14T00:24:56.437

Firstly, srand()/rand() commonly have a period of 2^32, which means that after calling srand(), rand() will internally iterate over distinct integers during the first 2^32 calls to rand(). Still, rand() may well return a result with less than 32 bits: such as an int between 0 and RAND_MAX where RAND_MAX is 2^31-1 or 2^15-1, so you may see repeated results as the caller of rand(). You probably read about the period though, or somebody's comment made with awareness of that, and somehow it's been mistaken as uniqueness....

Secondly, given any call to rand() generates a number far larger than you want, and you're doing this...

number1 % max

The result of "number1 % max" is in the range 0 <= N <= max, but the random number itself may have been any multiple of max greater than that. In other words, two distinct random numbers that differ by a multiple of max still produce the same result for number1 % max in your program.

To get distinct random numbers within a range, you could prepopulate a std::vector with all the numbers, then std::shuffle them.

How to make Random Numbers unique

6 Answers6

Linked

Related