Hatefiend Hatefiend - 2 months ago 10
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.

Answer

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");
Comments