Thread: Theory of preventing duplication (arrays not linked lists)

  1. #1
    Registered User
    Join Date
    Aug 2002
    Posts
    55

    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?

    Thanks in advance.

    John.
    Last edited by John.H; 02-05-2003 at 09:34 AM.

  2. #2
    Registered User
    Join Date
    Aug 2002
    Posts
    55
    Hmmm at smilies in the code tags? lol

    John.

  3. #3
    pronounced 'fib' FillYourBrain's Avatar
    Join Date
    Aug 2002
    Posts
    2,297
    a sort and single pass should take care of it.

    quicksort first

    single pass would check for something being equal to next in list.
    "You are stupid! You are stupid! Oh, and don't forget, you are STUPID!" - Dexter

  4. #4
    Registered User
    Join Date
    Jan 2003
    Posts
    311
    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. #5
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    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 numAlreadyFound = 0;
    int candidate;
    
    //the first candidate is automatically entered into unique[0];
    candidate = rand(() % MAX;
    unique[0] = candidate;
    numAlreadyFound++;
    
    
    //as long as total number is less than MAX
    while(numAlreadyFound < 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;
      }
    
      //if current candidate not found in array
      if(i == numAlreadyFound)
         //add it to the end of the values already found and increment 
         //numAlreadyFound
         unique[numAlreadyFound++] = candidate;
    }

  6. #6
    Registered User
    Join Date
    Aug 2002
    Posts
    55
    Thanks for replies folks. Got a lot to go on now. I'll have a read in a bit and see what the result is.

    Thanks again,

    John.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Doubly linked lists
    By mohanlon in forum C Programming
    Replies: 8
    Last Post: 12-08-2010, 01:01 AM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. Questions on Linked Lists
    By Weng in forum C++ Programming
    Replies: 1
    Last Post: 11-29-2003, 01:17 AM
  4. linked lists / arrays
    By akira in forum C++ Programming
    Replies: 0
    Last Post: 11-27-2001, 01:01 AM
  5. arrays, linear linked lists and binary trees
    By jasingle in forum C++ Programming
    Replies: 2
    Last Post: 11-12-2001, 11:12 AM