1. ## Theory of preventing duplication (arrays not linked lists)

Hey all.

I know the actual topic of duplication (especially the removal of duplicates in arrays), is a common thread on this board. However, my question is more to do with efficiency than a piece of code that works.

Here's what I'd like to do at the moment, but I'm asking for future reference more than anything, as the efficiency isn't really a problem pertaining to this example.

I need to initialise an array with the values 0 - 9 in a random order, without any duplicates. Obviously, placing a seed, and then using rand() % 10 will start things off. Thing is, when it comes to preventing the duplication, the only way I can think of doing it, is with nested loops. Something like (untested):

(Code now without smilies in it lol)

Code:
```#include <iostream.h>
#include <stdlib.h>
#include <time.h>

const int ARR_SIZE = 10;

int *init_arr(void);

int main(void)
{
int *aptr;

aptr = init_arr();

/* Cool program type stuff goes here. */

return 0;
}

int *init_arr(void)
{
int i, j;
static int rvals[ARR_SIZE];

srand(time(NULL));

for (i = 0; i < ARR_SIZE; )
{
rvals[i] = (rand() % 10);
for (j = 0; j < i; )
{
if (rvals[i] == rvals[j])
break;
else
j++;
}
if (j == i)
i++;
}

return rvals;
}```
The approach seems fine for something on such a small scale, but is there a more efficient way to tackle this for a program on a much larger scale?

John.

2. Hmmm at smilies in the code tags? lol

John.

3. a sort and single pass should take care of it.

quicksort first

single pass would check for something being equal to next in list.

4. The standard library provides std::random_shuffle(), I suggest you use it. There are many ways to do this, many of them are easy to get subtly wrong. The easy way to do this is sort the array(or generate a sorted array), remove duplicates and then starting from the last element, swap the current position with any element less than or equal to the current position and decrement the current position. Choice of random number generators and method of seeding rng's is also important if you want to really get this perfect. To shuffle 13 elements and get all !13 possiblities you need log2(!13) ~= 32.54 bits of state. With 32 bits you get 'only' 4 billion possible shuffles. This sends us off into thorough geekdom at such fun places as pLab

5. Since you eventually want an array filled with unique instances of a given value type, you could use an STL set, instead of an array, to ensure unique instances, and then read the values of the set back into the array later, or create your own selection algorhithm. Maybe something like this:

Code:
```const MAX = 10;
int unique[MAX];
int i;
int candidate;

//the first candidate is automatically entered into unique[0];
candidate = rand(() % MAX;
unique[0] = candidate;

//as long as total number is less than MAX
{
//generate new candidate
candidate = rand() % MAX;

//check each value in array against current candidate value
for(i = 0; i < numAlreadyFound ; ++i)
{
//if current candidate already exists in the array
if(unique[i] == candidate)
//stop looking at values in array
i = 1000;
}