Random array generation with no duplicates

问题:

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.

回答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]);
    }
}

回答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.

回答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.

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

回答5:

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() );

回答6:

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.

回答7:

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.

回答8:

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.

回答9:

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.