Generating exactly certain number of unique random numbers from a specific range

Question

Consider I am given a specific range (0 to 5,000,000) and I should generate 2,500,000 unique random numbers from this range. What is an efficient way to do this? I understand that is tough to get true random numbers.

I tried by checking if a number exists so that I can generate a new random number. But it takes hours to compute. Is there a better way to do this.

The reason behind this is, I have a vector of size 5,000,000. I want to shrink the vector exactly by half. i.e. delete random 50% of the elements from the vector.

    #include <iostream>
    #include <vector>
    #include <stdlib.h>
    #include <algorithm>
    using namespace std;

    #define NUMBER 2500000
    #define RAND_START 0
    #define RAND_END 5000000

    unsigned int generate_random_number(int min, int max)
    {
        return min + (rand() % (unsigned int)(max - min + 1));
    }

    int main(int argc, char* argv[])
    {
        unsigned int count = 0, random_number;
        vector<unsigned int> rand_vector;
        do 
        {   
            count++;
            random_number = generate_random_number(RAND_START,RAND_END);
// Tried to manually add a different number each time. But still not a considerable improvement in performance. 
            if (std::find(rand_vector.begin(), rand_vector.end(), random_number) != rand_vector.end())
            {
                if(random_number > count)
                    random_number = random_number - count;
                else
                    random_number = random_number + count;          
            }
            rand_vector.push_back(random_number);
            sort(rand_vector.begin(), rand_vector.end());
            rand_vector.erase(unique (rand_vector.begin(), rand_vector.end()), rand_vector.end());
        }while (rand_vector.size() != NUMBER);


        for (unsigned int i =0; i < rand_vector.size(); i++)
        {
            cout<<rand_vector.at(i)<<", ";
        }
        cout<<endl;
        return 0;
    }

Any better approach by which I can do this?

Answer 1

You seem to be locked on an idea that you have to pre-generate your random numbers somehow. Why? You said that the ultimate task is to delete some random elements from a vector. For that specific problem it is not necessary to pre-generate all random indices in advance. You can simply generate these indices "on the fly".

For this specific task (i.e. delete 50% of elements in the vector), Knuth algorithm will work pretty well (see https://stackoverflow.com/a/1608585/187690).

Just iterate through all elements of the original vector from 0 to N-1 and make a random decision to delete i-th element with the probability of N_to_delete / N_to_iterate, where N_to_delete is the number of elements that still have to be deleted, and N_to_iterate is the length of the remaining portion of the vector. This approach does it in one pass (if implemented smartly), requires no extra memory and no trial-and-error iterations. It simply does exactly what you want it to do: destroys 50% of vector elements with equal probability.

Knuth algorithm works best in situations when the number of random values (M) is fairly large compared to the length of the range (N), since its complexity is tied to N. In your case, where M is 50% of N, using Knuth algorithm is a pretty good idea.

When the number of random values is much smaller than the range (M << N), Bob Floyd algorithm (see the above link) makes more sense, since its complexity is defined by M and not by N. It requires additional memory (a set), but still makes no trial-and-error iterations when generating random numbers.

However, in your case you are trying to delete elements from a vector. Vector element deletion is dominated by N, which defeats the benefits of Bob Floyd algorithm anyway.

Answer 2

Instead of doing a manual check if you have unique numbers, you could use e.g. std::unordered_set and continue generating numbers until the size of the set is the number of numbers you want.

Answer 3

Easiest way to code it:

std::random_shuffle(vectoshrink.begin(), vectoshrink.end());
vectoshrink.resize(vectoshrink.size() / 2);

If you want to maintain the order of the elements in vectoshrink use AndreyT's answer.

If you really do want to select the indexes in advance:

std::vector<size_t> vec(vectoshrink.size());
// iota is C++11, but easy to do yourself
std::iota(vec.begin(), vec.end(), size_t(0));
std::random_shuffle(vec.begin(), vec.end());
vec.resize(vec.size() / 2);
// optionally
std::sort(vec.begin(), vec.end());

Now, you could use those indexes to shrink your original vector by copying the elements at the indexes in vec into a new vector, and swap the result with the original.

In both cases, random_shuffle does more than is strictly required, since it shuffles the whole vector, whereas actually we only need to "shuffle" half of it. If you read how a Fisher-Yates shuffle works, though, it's easy to see that if you code it yourself then the only modification required is to do half as many steps as the full shuffle. C++ doesn't have a standard partial_random_shuffle, though.

Finally, beware that the default random source might not be very good, so you might want to use the three-argument version of random_shuffle. Your generate_random_number function is quite biassed for certain values of min and max, so you might want to research a bit more on the general theory of random number generation.

Answer 4

Generate 1st number <5M, 2nd number <(5M-1), etc. Each time after you remove element, you'll have one element less and you don't care if it's the same number. ;-) This doesn't answer your question about unique numbers, but about halving your vector.

And you will not have to generate more numbers than you need.