Random array generation with no duplicates

Solution 1:

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.

Solution 2:

First of all rand() is generatig random numbers but not wihout duplicates.

If you want to generate a random array without duplicates the rand() method is not working at all.

Let say you want to generate an array of 1000 numbers. In the best case let say you generated the first 999 numbers without duplicates and last think to do is generating the last number. The probability of getting that number is 1/1000 so this is almost going to take forever to get generated. In practice only 10 numbers makes a big trouble.

The best method is to generate all your numbers by incrementation (or strictly monotonic sequence) is shuffle them. In this case there will be no duplicates

Here is an exemple on how to do it with 10 numbers. Even with 1000 numbers it's working.

Note: Suffle function from Jhon Leehey's answer.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void shuffle(int *arr, size_t n)
{
    if (n > 1) 
    {
        size_t i;
        srand(time(NULL));
        for (i = 0; i < n - 1; i++) 
        {
          size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
          int t = arr[j];
          arr[j] = arr[i];
          arr[i] = t;
        }
    }
}

int main()
{
    int i;
    int arr[10];
    for (i=0; i<10; i++){
        arr[i] = i;
    }
    shuffle(arr, 10);
    for (i=0; i<10; i++){
        printf("%d ", arr[i]);
    }
}

Solution 3:

There are 2 solutions to choose from:

1. Generate random numbers using something like rand() and check for duplicates.

2. Find a mathematical sequence that is strictly monotonic (preferably strictly increasing) and get its terms as members of your array. Then, you can shuffle your array. The result will not be truly random, but neither using rand() won't. rand() uses a simillar tehnique, and that is why we need to set the seed with something changeing, like time. You can use time for example to generate the first element of the sequence, and with a good sequence your results will be at least decent. Note that the sequence MUST be strictly monotonic, to avoid generation of duplicates. The sequence need not be too complex. For example, if you get unix time modulo 10000 as the first term and then you generate other terms using a reccurence like x[i] = x[i-1] + 3*x[i-2] should be fine. Of course, you may use more sophisticated sequences too, but be careful at overflow (as you can't apply modulo operator to the result, because it would not be increasing anymore) and the number of digits you would like to have.

Solution 4:

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