Creating an array filled with random unique numbers

Question

So i'm trying to create an array of 4 items that is randomly filled with 4 unique numbers. Currently I have a hugely long while loop which checks each value in the array and keeps repeating if they are the same. It's really badly coded and I was wondering if you guys could help me figure out a better way? Here's what I currently have.

int array[4];
while(array[0] == array[1] || array[1] == array[2] ||  array[2] == array[3] || array[0] == array[2] || array[0] == array[3] || array[1] == array[3])
{
    array[0] = rand() % 20;
    array[1] = rand() % 20;
    array[2] = rand() % 20;
    array[3] = rand() % 20;
}

Do some research about [the *set* data structure](https://en.wikipedia.org/wiki/Set_(abstract_data_type)). — Some programmer dude, Sep 08 '18 at 05:53
Why to you reroll all values if e.g. only two are identical? — Yunnosch, Sep 08 '18 at 05:58
@Someprogrammerdude Interesting, but please help me understand how that supports a solution. Assuming a well-implemented set is available, how would that support creating four different randoms efficiently? I.e. more efficient or easy than in an array. — Yunnosch, Sep 08 '18 at 06:01
In pseudo-code: `while (size_of_set() < N) { insert_into_set(get_random_value()); }` If you translate into real code, then afterwards you are guaranteed to have a set of `N` unique random numbers. Much easier to understand the logic, no need for excessive conditions, and scales very well (code-wise) as `N` could be `4` or `10000` and the code won't change. — Some programmer dude, Sep 08 '18 at 06:03
@Someprogrammerdude I've never heard of or used sets before, how would I check a value in a set? Is it the same as an array? — crooose, Sep 08 '18 at 06:12

Maxime Chéramy · Accepted Answer · 2018-09-08T08:09:13.070

Here's an algorithm to generate your array of 4 distinct numbers from 0 to 20 which is O(n + m) with n the 4 numbers and m the 20 possible values:

Create an array randArr of 20 integers: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19}. This is the array used to pick random numbers
array is an array of 4 integers that will contain the result
for i going from 0 to 3 (included):
- Pick a random number r between i and 19 (inclusive). Swap randArr[r] and randArr[i]
- Copy to array: array[i] = randArr[i]

Here's the implementation (with a slight improvement to merge the last 2 steps):

int randArr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19};
int array[4];
for (int i = 0; i < 4; i++) {
        int r = i + rand() % (20 - i);
        array[i] = randArr[r];
        randArr[r] = randArr[i];
}

https://tech.io/snippet/dGgblEO

P.W · Answer 2 · 2018-09-08T07:06:39.497

You want generate random numbers from 0 to 19 and fill them in the array without any duplicates.
Since you have not initialized the elements of array, it is possible that the uninitialized values are already distinct from each other. In this case, the while loop will not be executed at all.

Secondly, you are generating random values for every element of the array every time when any two of them match. This is not required. You have to regenerate the random number only for the element that matches any of the existing ones. This is what a set structure (mentioned in the comments) does.

To shuffle an array of n elements, Fisher–Yates shuffle Algorithm is used which works in O(n) time complexity.

In your case, take an initial array of values from 0 to 19. Once you have shuffled this array, you can take the any k elements of this array (in your case k = 4) and use them (They will be distinct). Implementations of this algorithm can be found online.

Creating an array filled with random unique numbers

2 Answers2