Random array generation with no duplicates

Question

I am trying to create something that generates a random array with no duplicate values. I've already looked at other answers but none seem to help me understand. I cannot think of a way to actually generate random numbers that contain no duplicates. Here is what i have tried so far:

srand(time(NULL));
int numbers [4];

for (int x=0; x!=4;x++)
{
    numbers[x] = 1 + (rand() % 4) ;
    printf("%d ", numbers[x]);
}

Any help will be appreciated.

Answer 1

After you generate each random number, loop through the previous values and compare. If there's a match, re-generate a new value and try again.

Answer 2

How about this:

#define NUMS (10)

int randomSequence[NUMS] = {0}, i = 0, randomNum; 
bool numExists[NUMS] = {false};

while(i != NUMS)
{
    randomNum = rand() % NUMS;

    if(numExists[randomNum] == false)
    {
        randomSequence[i++] = randomNum;
        numExists[randomNum] = true;
    }
}

Of course, the bigger NUMS is, the longer it will take to execute the while loop.

Answer 3

You can use your own random number generator which has the sequence greater or equal to length of the array. Refer to http://en.wikipedia.org/wiki/Linear_congruential_generator#Period_length for instructions.

So you need LCG with expression Xn+1 = (aXn + c) mod m. Value m must be at least as large as length of the array. Check "if and only if" conditions for maximum sequence length and make sure that your numbers satisfy them.

As a result, you will be able to generate random numbers with satisfactory randomness for most uses, which is guaranteed to not repeat any number in the first m calls.

Answer 4

In c++, all you need is:

std::random_shuffle()

http://www.cplusplus.com/reference/algorithm/random_shuffle/

int numbers [4];

for (int x=0; x!=4;x++)
{
    numbers[x] = x;
}

std::random_shuffle(numbers, numbers +4);

Update: OK, I had been thinking that a suitable map function could go from each index to a random number, but thinking again I realize that may be hard. The following should work:

    int size = 10;
    int range = 100;

    std::set<int> sample;

    while(sample.size() != size)
        sample.insert(rand() % range); // Or whatever random source.

    std::vector<int> result(sample.begin(), sample.end());

    std::random_shuffle ( result.begin(), result.end() );

Answer 5

You start off filling a container with consecutive elements beginning at 0

std::iota(begin(vec), end(vec), 0);

then you get yourself a decent random number generator and seed it properly

std::mt19937 rng(std::random_device{}());

finally you shuffle the elements using the rng

std::shuffle(begin(vec), end(vec), rng);

live on coliru

---

On some implementations random_device doesn’t work properly (most notably gcc on windows) and you have to use an alternative seed, i.e. the current time → chrono.

Answer 6

srand(time(NULL));
const int N = 4;
int numbers [N];

bool isAlreadyAdded(int value, int index)
{
     for( int i = 0; i < index; i ++)
          if( numbers[i] == value)
              return true;
     return false;
}
for (int x=0; x!=N;x++)
{
    int tmp = 1 + (rand() % N) ;
    while( x !=0 && isAlreadyAdded(tmp, x))
           tmp = 1 + (rand() % N) ;

    numbers[x] = tmp;
    printf("%d ", numbers[x]);
}

It's just a way. it should work, of course there are better ways