DaniWeb Forum Index > Software Development > C++

Help needed filling array with unique random numbers

Please support our C++ advertiser: Intel Parallel Studio Home

Last »

•

Join Date: Aug 2005

Posts: 5,273

Reputation: iamthwee is a splendid one to behold

Solved Threads: 378

iamthwee

Offline

Posting Expert

Re: Help needed filling array with unique random numbers

#11

Apr 15th, 2007

That has a very bad efficiency though. See my suggestion.

*Voted best profile in the world*

•

Join Date: Dec 2006

Posts: 1,089

Reputation: vijayan121 is a name known to all

Solved Threads: 164

vijayan121 vijayan121 is offline

Offline

Veteran Poster

Re: Help needed filling array with unique random numbers

#12

Apr 15th, 2007

•

Originally Posted by iamthwee

Can't you just create an array of 5000 ints
Help with Code Tags

C++ Syntax (Toggle Plain Text)
for (int i =0; i< 5000; i++ )
{
   array[i] =i;
}
for (int i =0; i< 5000; i++ ) { array[i] =i; }
Then shuffle them around. So you would be picking two random index positions and swapping them. Do this say a couple of hundred times.

Then just print out the first 200 elements and you will get 200 random elements with no repeats in a number range from 0 - 5000.

This would be time-efficient and space-inefficient.

•

Join Date: May 2006

Posts: 1,580

Reputation: Infarction has a spectacular aura about

Solved Threads: 52

Infarction Infarction is offline

Offline

Battle Programmer

Re: Help needed filling array with unique random numbers

#13

Apr 15th, 2007

iamthwee makes a good point. The fix I provided will only be moderately effective at best, with decreasing effectiveness as you try to build a longer list (since you have to search the list each time and have more chances of a duplicate).

Also, neither of these will work if you were to build a list over 5000, for obvious reasons. And by disallowing duplicates, the array is technically not random

•

Join Date: Aug 2005

Posts: 5,273

Reputation: iamthwee is a splendid one to behold

Solved Threads: 378

iamthwee

Offline

Posting Expert

Re: Help needed filling array with unique random numbers

#14

Apr 15th, 2007

>This would be time-efficient and space-inefficient.

Maybe, but for a newbie my way is easier to understand.

Last edited by iamthwee; Apr 15th, 2007 at 5:52 pm.

*Voted best profile in the world*

•

Join Date: Apr 2007

Posts: 7

Reputation: bling_bling_vr6 is an unknown quantity at this point

Solved Threads: 0

bling_bling_vr6 bling_bling_vr6 is offline

Offline

Newbie Poster

Re: Help needed filling array with unique random numbers

#15

Apr 15th, 2007

Wow, thanks vijayan that IS wonderful. Thank you all so much for your help and clever ideas. I definately feel that I have what i need to get past the hurdle I was stuck on. Thank you to iamthewee too. I appreciate your help

•

Join Date: Jun 2006

Posts: 7,642

Reputation: ~s.o.s~ has much to be proud of

Solved Threads: 471

~s.o.s~

Offline

Failure as a human

Re: Help needed filling array with unique random numbers

#16

Apr 15th, 2007

•

Originally Posted by Infarction

To fix that, you should put the random generator in a loop and use the LinearSearch results as a loop condition:
Help with Code Tags

C++ Syntax (Toggle Plain Text)
for(int i = 0; i < MAXSIZE; i++)
{
  do {
    temp = rand() % 5000; // get random number
  } while (LinearSearch(list, temp) != -1); // repeat till it's unique
  list[i] = temp; // save it
}
for(int i = 0; i < MAXSIZE; i++) { do { temp = rand() % 5000; // get random number } while (LinearSearch(list, temp) != -1); // repeat till it's unique list[i] = temp; // save it }

•

Originally Posted by ~s.o.s~

• The loop counter in the loop which generates random numbers should not be incremented if a duplicate in found in the list.

I don't accept change; I don't deserve to live.

Jo Tujhe Jagaaye, Nindein Teri Udaaye Khwaab Hai Sachcha Wahi.
Nindon Mein Jo Aaye Jise To Bhul Jaaye Khawab Woh Sachcha Nahi.
Khwaab Ko Raag De, Nind Ko Aag De

•

Join Date: Mar 2008

Posts: 2

Reputation: loveloic is an unknown quantity at this point

Solved Threads: 0

loveloic

Offline

Newbie Poster

Re: Help needed filling array with unique random numbers

#17

Mar 14th, 2008

Hi vijayan121,

I think you may be able to help me, I haven't touched a line C in years, but the algorithm is what interests me, not the syntax. I guess the same must be doable in java.

Anyhow, I've got the same requirement, and my problem is the performance, it takes ages for my code to produce me my list.

I was suspecting that it was not the best solution to iterate over the list of elements to check if the random number was not taken yet and in that case regenerating a random number. From what I understand, your code should do the trick far quicker.

However, I am having some trouble understanding the logic. Could you pls elaborate? What does 'M' represent? What is obstream? Any chance you could give us more explanationsK? Thanks!

•

Join Date: Dec 2006

Posts: 1,089

Reputation: vijayan121 is a name known to all

Solved Threads: 164

vijayan121 vijayan121 is offline

Offline

Veteran Poster

Re: Help needed filling array with unique random numbers

#18

Mar 14th, 2008

> What does 'M' represent?
M is the cardinality of the set of numbers out of which we have to choose N *unique* numbers. (M>=N)

> Any chance you could give us more explanations?
a. probability that the first number is chosen is N/M b. probability that the second number is chosen is (N-1)/(M-1) if the first was chosen,
N/(M-1) if it was not.
ie. N/M * (N-1)/(M-1) + (M-N)/M * N/(M-1) == N/M and so on.

here is a java transliteration of the alogorithm (caveat: java is a foreign language to me, there may be syntax errors. but the logic is sound).

 Help with Code Tags 
 java Syntax (Toggle Plain Text) 
public class unique_rand_generator 
{
	// fill up array with unique random integers 
	// from the range min_value .. max_value
        // invariant: max_value - min_value + 1 (M) 
        //      >= array.length (N)
    public static void fill( int[] array, int min_value, 
                             int max_value )
	{
	  int available = max_value - min_value + 1 ;
	  int required = array.length ;
          Random rng = new Random() ;
	  for( int i=0 ; i<available ; ++i )
	  {
		// we have to choose required
                // out of the remaining (available-i)
	    if( ( rng.nextInt(available-i) ) < required )   
	    {
	      --required ;
	      array[required] = min_value + i ;
	    }
	  }
	}
}
public class unique_rand_generator 
{
	// fill up array with unique random integers 
	// from the range min_value .. max_value
        // invariant: max_value - min_value + 1 (M) 
        //      >= array.length (N)
    public static void fill( int[] array, int min_value, 
                             int max_value )
	{
	  int available = max_value - min_value + 1 ;
	  int required = array.length ;
          Random rng = new Random() ;
	  for( int i=0 ; i<available ; ++i )
	  {
		// we have to choose required
                // out of the remaining (available-i)
	    if( ( rng.nextInt(available-i) ) < required )   
	    {
	      --required ;
	      array[required] = min_value + i ;
	    }
	  }
	}
}

Last edited by vijayan121; Mar 14th, 2008 at 9:55 am.

•

Join Date: Mar 2005

Posts: 464

Reputation: invisal is a jewel in the rough

Solved Threads: 49

invisal

Offline

Posting Pro in Training

Re: Help needed filling array with unique random numbers

#19

Mar 14th, 2008

My algorithm is a little bit different. First, I generate the random number into the array in order. Then randomly swap the array elements to make it disorder. For example: I want to generate 11 unique numbers from range of 1 to 1000. Firstly, I would fill my array with random number in order by create recursive function that firstly random a number into the middle of the array. Then, on the left side of that number I generate the number from 1-random_number and on the right side of that number I generate the number from random_number to max_number.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
___  ___  ___  ___  ___  ___   320  ___  ___  ___  ___  ___  ___
___  ___  150  245  ___  ___
16    85
                    270   290
                                    ___  ___  570  630  ___  ___
 
                                    421  524
 
                                                        724  815
16   85   150  245  270  290  320   421  424  570  630  724  815
___  ___  ___  ___  ___  ___   320  ___  ___  ___  ___  ___  ___
___  ___  150  245  ___  ___
16    85
                    270   290
                                    ___  ___  570  630  ___  ___

                                    421  524

                                                        724  815
16   85   150  245  270  290  320   421  424  570  630  724  815

However, this algorithm has its weak point, what happen if the first number is 1, but we can easily solve that problem.

Yesterday is a history, tomorrow is a mystery, today is a gift.
Behind every smile is a tear.
Visal .In

•

Join Date: Oct 2007

Posts: 269

Reputation: sarehu is on a distinguished road

Solved Threads: 22

sarehu

Offline

Posting Whiz in Training

Re: Help needed filling array with unique random numbers

#20

Mar 14th, 2008

The trouble with that algorithm is that it doesn't uniformly select all the possible combinations of numbers; it's biased. The trouble with vijayan's algorithms is that they rely on walking through all the possible numbers one must select from, which is slow.