Hatefiend - 1 year ago 103
C Question

# C - Generate random array with no repeats without shuffling

I want to generate an array of

`1,000,000`
integers without repeats without shuffling. This means that I don't want to do:

``````int arr[1000000];
for (int i = 0; i < 1000000; i++)
{
arr[i] = i;
}
shuffle(arr);
shuffle(arr);
// Done.
``````

I want to figure out a way how to do it without using that technique. I also don't want to randomly select an index between
`1`
and
`1,000,000`
because at number
`999,999`
there would be only a
`1/1,000,000`
chance to continue.

I've been trying to think of a solution and I think the key is parallel arrays and looping backwards then using modulus to limit only to the indexes that you haven't already been to, but then I can't guarantee that the value I get is unique. I don't want to use a HashSet or TreeSet implementation as well.

This can be done in `O(n)` time with two lists, one with the number (initialy) in order, and one in the resulting order.

You start with `n` elements in order in your source list. Then you select a random number mod `n`. That gives you the next element, which you place in the destination list.

Now the key part. If you were to pick a random number between `0` and `n-1` each time, as you seem to think a shuffle does, you have an increasing chance of selecting a number you selected before. So how do you handle this? By decreasing the available list of number to select from.

In the source list, after selecting a number, you move the last element of the list to the index that was just used. You now have a list of `n-1` numbers to chose from. So on the next iteration you take a random number mod `n-1`. Keep going until your source list only has one element.

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

#define LEN 10

int main()
{
int a[LEN], b[LEN];
int i, val;
int count = LEN;

srand(time(NULL));

for (i=0;i<LEN;i++) {
a[i]=i+1;
}
for (i=0;i<LEN;i++) {
val = rand() % count;
b[i] = a[val];
a[val] = a[count-1];
count--;
}
for (i=0;i<LEN;i++) {
printf("%d ", b[i]);
}
printf("\n");

return 0;
}
``````

EDIT:

Here's a slightly more efficient version that doesn't use two arrays and is therefore `O(1)` space:

``````int a[LEN];
int i, val, tmp;

srand(time(NULL));

for (i=0;i<LEN;i++) {
a[i]=i+1;
}
for (i=0;i<LEN-1;i++) {
val = (rand() % (LEN - 1 - i)) + i + 1;
tmp = a[i];
a[i] = a[val];
a[val] = tmp;
}
for (i=0;i<LEN;i++) {
printf("%d ", a[i]);
}
printf("\n");
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download