Hatefiend - 1 year ago 54

C Question

I want to generate an array of the sequence

`[0...1'000'000]`

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

I want to figure out how to do it without the "black-box"

`shuffle`

`1`

`1'000'000`

`999'999`

`1/1'000'000`

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 Source

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