7

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]);
}
janw
  • 8,758
  • 11
  • 40
  • 62
user3128016
  • 101
  • 1
  • 1
  • 3

9 Answers9

19

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.

Darklighter
  • 2,082
  • 1
  • 16
  • 21
9

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]);
    }
}
Community
  • 1
  • 1
rullof
  • 7,124
  • 6
  • 27
  • 36
  • 1
    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. – Edge7 Dec 22 '13 at 23:45
  • When i said incrementation i didn't means exactly [0-N] it could be a strictly monotonic sequence. – rullof Dec 22 '13 at 23:49
  • You could not count on probability to get such precise value. Different behaviours on different runtimes (it could take 10sec, ..., 1hour, of forever) – rullof Dec 22 '13 at 23:51
  • 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. – user3128016 Dec 23 '13 at 11:07
  • @rullof Thanks for your help and hopefully solving my second doubt, Luis – user3128016 Dec 23 '13 at 11:08
  • You want to get 4 numbers between 0 and 9? – rullof Dec 23 '13 at 11:13
  • The call to `srand()` **must not** be inside the `shuffle()` function. It isn't in Jhon Leehey's answer linked to. – pmg Apr 07 '16 at 08:06
2

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.

Paul92
  • 8,827
  • 1
  • 23
  • 37
  • I really like this answer. I used first solution you propose in my answer. – Edge7 Dec 22 '13 at 23:09
  • Yes, that is why i have not insisted on that one :). – Paul92 Dec 22 '13 at 23:11
  • @Edge7 the rand() method is not working at all (check my answer to see why)! – rullof Dec 22 '13 at 23:33
  • @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 – Edge7 Dec 22 '13 at 23:39
  • @Edge7 is his code he writen `nambers[x] = 1 + rand()` so he is absolutly trying to get the numbers 1 2 3 randomised – rullof Dec 22 '13 at 23:44
  • @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). – Paul92 Dec 22 '13 at 23:46
  • I just think that @user3128016 should add details – Edge7 Dec 22 '13 at 23:50
1
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

Edge7
  • 681
  • 1
  • 15
  • 35
  • 1
    As C++ programmers we should [avoid `rand`](http://www.azillionmonkeys.com/qed/random.html) particularly when we now have the [`` header](http://en.cppreference.com/w/cpp/header/random) – Mgetz Dec 22 '13 at 23:18
  • 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" – Edge7 Dec 22 '13 at 23:27
1

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.

Fiddling Bits
  • 8,712
  • 3
  • 28
  • 46
0

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() );
Keith
  • 6,756
  • 19
  • 23
  • This doesn't answer the question at all. – Rapptz Dec 22 '13 at 22:39
  • 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. – Mark Dec 22 '13 at 22:39
  • 2
    @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. – Keith Dec 22 '13 at 22:41
  • @Keith don't use `rand` it's not really random use one of the algorithms out of the `` header. – Mgetz Dec 22 '13 at 22:56
  • 1
    @Mgetz Hence the comment re the random source; I did not see that as the interesting bit here. – Keith Dec 22 '13 at 22:57
  • @Keith people sadly use examples given in answers, we shouldn't be propagating bad practices. – Mgetz Dec 22 '13 at 22:59
  • @Mgetz I've used srand instead of rand... and whats wrong there –  Dec 22 '13 at 23:05
  • 1
    @ĐēēpakShãrmã [This article explains what is wrong with `rand`](http://www.azillionmonkeys.com/qed/random.html) `srand` just seeds `rand` and is not thread safe in any case. – Mgetz Dec 22 '13 at 23:15
  • @ĐēēpakShãrmã a better way is to use the [`` header](http://en.cppreference.com/w/cpp/header/random) – Mgetz Dec 22 '13 at 23:21
0

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.

Zoran Horvat
  • 10,924
  • 3
  • 31
  • 43
0

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.

Bryan Polyak
  • 40
  • 2
0

If you want to pseudo-randomly traverse a large space without maintaining visited indices, you should look at this project I contributed to years ago for the basic technique. http://packetfactory.openwall.net/projects/ipspace/index.html

You should be able to adapt it to your purposes, source is at the bottom of the page.

ibtaylor
  • 31
  • 2