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.

Solution 1

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 2

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 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

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.

Solution 5

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

View more solutions

Comments

[Rapptz]

This doesn't answer the question at all.

[Mark]

This will give you the numbers from 0 to 3, randomly shuffled. If you need a wider distribution, you'll need to use some other method.

[Keith]

@Rapptz Depends on the reading of the example vs the wording of the question. Further, the random shuffle could be used to generate the general case easily enough. OP, please clarify the required range of the targets.

[Mgetz]

@Keith don't use rand it's not really random use one of the algorithms out of the <random> header.

[Keith]

@Mgetz Hence the comment re the random source; I did not see that as the interesting bit here.

[Mgetz]

@Keith people sadly use examples given in answers, we shouldn't be propagating bad practices.

[Admin]

@Mgetz I've used srand instead of rand... and whats wrong there

[Edge7]

I really like this answer. I used first solution you propose in my answer.

[Paul92]

Yes, that is why i have not insisted on that one :).

[Mgetz]

@ĐēēpakShãrmã This article explains what is wrong with rand srand just seeds rand and is not thread safe in any case.

[Mgetz]

As C++ programmers we should avoid rand particularly when we now have the <random> header

[Mgetz]

@ĐēēpakShãrmã a better way is to use the <random> header

[Edge7]

You are right, I used rand() because I didn't want to change much of his code, but just say "Check previous values you already added"

[rullof]

@Edge7 the rand() method is not working at all (check my answer to see why)!

[Edge7]

@rullof I think the question is not clear. If the question is fill in an array (size N) with random not duplicates values (0 <= value < N), likely my solution will be very very slowly, maybe too slowly, but if the constraint ( 0 <= value < N) is no longer needed, my solution starts to be acceptable

[rullof]

@Edge7 is his code he writen nambers[x] = 1 + rand() so he is absolutly trying to get the numbers 1 2 3 randomised

[Edge7]

If the following constraint is true, you are right: "Random values in [0, N) with N array size". But if it's not true and array can be fitted with value greater than N and N is much less than rand() codomain, you are wrong.

[Paul92]

@rullof the rand method is working if you have enough room (let's say you want 1000 numbers from 0 to 1000000) in decent time. Of course, your answer is right, but there are cases when it works fine. Also, the checking may be implemented in O(1) complexity (sacrificing some space). But the other solution is the second one i described (note that incrementation is basically a sequence).

[rullof]

When i said incrementation i didn't means exactly [0-N] it could be a strictly monotonic sequence.

[Edge7]

I just think that @user3128016 should add details

[rullof]

You could not count on probability to get such precise value. Different behaviours on different runtimes (it could take 10sec, ..., 1hour, of forever)

[Admin]

Hi @rullof i tried your code and it seems to work correctly but i'd like to actually understand how it works as i am not entirely sure how it does all the random number generation. Is there any chance you could give me a more standard explanation as i have recently started to have to program with C and i am struggling quite a bit. Also, do you know if there is any way i could get it to do the array of random numbers of length four but including all integers up to 9? Because if i change the length to 4 it only prints the integers {0,1,2,3,4} but it would be helpful if it actually printed all 9.

[Admin]

@rullof Thanks for your help and hopefully solving my second doubt, Luis

[rullof]

You want to get 4 numbers between 0 and 9?

[pmg]

The call to srand() must not be inside the shuffle() function. It isn't in Jhon Leehey's answer linked to.