Random Number Generation

[shank8]

I was wondering if anyone knows an easy way to generat random numbers, but in a sequence so that no random number is used more than once? I only need to generate under 50 random numbers or so. i.e. with a set = {1,2,3,4,5} I want to generate a random sequence like {3,5,1,4,2} where no numbers show up more than once. Thanks

[rtzoeller]

This should work for your needs. Let me know if you have problems with it. Also, you may be able to optimize it further.

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

int main()
{
    srand(time(NULL)); // Set seed for random numbers
    vector<int> initialNumbers (50);
    vector<int> randomNumbers (50);
    int randomNumber;
    for (int i = 0;i<50;i++) // Set vector with the numbers 1-50
    {
        initialNumbers[i]=i+1;
    }
    for (int i = 0;i<50;i++) // Take a random member of initialNumbers and put it in randomNumbers, then erase that member from initialNumbers
    {
        randomNumber = rand() % (50-i);
        randomNumbers[i] = initialNumbers[randomNumber];
        initialNumbers.erase(initialNumbers.begin()+randomNumber);
    }
}

Also if you replace all places where 50 shows up with a variable you should be able to adjust how many numbers are generated.

[hamsterman]

A better idea is to use http://www.cplusplus.com/reference/algorithm/random_shuffle/ .

[shank8]

Thank you very much, this looks like it will work. Didn't know you could use that erase function for an array. Very handy!

[rtzoeller]

You should definitely use that algorithm if it works for you. I just wanted to give shank8 an idea of how to do it manually, because learning the underlying concept can teach you things useful for when there isn't a STL library for you to use.

[hamsterman]

@shank8, initialNumbers is not an array, it's an std::vector.

@rtzoeller, that's all well. It's just that your algorithm isn't very good. The link I posted shows an example implementation too.

[rtzoeller]

What about it isn't very good?

[hamsterman]

It uses two arrays. random_shuffle only needs the array you give it.
It calls erase many times. Erase itself has linear time complexity, so in the end, your algorithm will have a complexity somewhere between n²/2 and n. random_shuffle always has linear complexity.