Help needed filling array with unique random numbers

[bling_bling_vr6]

Hello, I need some help filling an array with UNIQUE random numbers. So far I've figured out how to fill an array with random numbers, that's easy, but I'm stuck on how to avoid filling it with duplicate values. I'm assuming that i'll have to use either a linear or binary search function while filling the array, but my attempts so far have failed. Anyone got any idea what i'm doing wrong? Here's my terrible code so far...any help would dearly be appreciated.

#include <iostream>
#include <string>
#include <cstdlib>
#include <iomanip>
using namespace std;

//Global constant declaration
const int MAXSIZE = 200;
const int SEED = 12;

//Function Prototypes
void Seed();
void FillMainList(int list[]);
void PrintArray(const int list[]);
int LinearSearch(const int list[], int value);

int main ()
{
    int list[MAXSIZE];
    Seed();
    FillMainList(list);
    PrintArray(list);
    return 0;
}

void Seed() //Set & Display the seed value
{
    srand(SEED);
}

void FillMainList(int list[])
{
    int temp, test;
    for (int i=0; i<MAXSIZE; i++)
    {
        temp = (rand() % 5000);
        test = LinearSearch(list, temp);
        if (test == -1)
        list[i] = temp;
    }
}

void PrintArray(const int list[])
{
        for (int i=0; i<MAXSIZE; i++)
        {
            cout << setw(5) << list[i] << endl;
        }
        cout << endl;
}
int LinearSearch(const int list[], int value)
{
    int index = 0;
    int position = -1;
    bool found = false;

    while (index < MAXSIZE && !found)
    {
        if (list[index] == value)
        {
            found = true;
            position = index;
        }
        index++;
    }
    return position;
}

[Infarction]

I don't see anything particularly wrong with your code. Two things I do see though:
- By using the same seed, you'll always get the same list of numbers. Most people solve this by using the current time as a seed.
- Using the global constant MAXSIZE is probably bad style. It's fine for creating the array, but you should restructure your other functions to take an array and it's size as parameters, and then use that size value for your loop condition. This will be more adaptable to different sized arrays and especially useful if you deal with dynamic arrays.

[~s.o.s~]

Some points:

• You need to tell us a bit more than the normal "this doesn't work" thing. What do you mean when you are not able to generate unique numbers? Is the array not filled completely or the numbers are getting repeated.

• You need to break out of the loop in your linear search if the required value is found.

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

• Use the current time as seed instead of a small number like 7 or 12.

[Infarction]

• You need to break out of the loop in your linear search if the required value is found.

He sets a boolean flag :icon_wink:

[bling_bling_vr6]

Some points:

• You need to tell us a bit more than the normal "this doesn't work" thing. What do you mean when you are not able to generate unique numbers? Is the array not filled completely or the numbers are getting repeated.

• You need to break out of the loop in your linear search if the required value is found.

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

• Use the current time as seed instead of a small number like 7 or 12.

So when I run my code I get these results (i truncated them) but as you can see I get some weird memory location for whenever the number is a duplicate...I think or something weird is happening here.

2260
-858993460
-858993460
1745
4438
2603
4623
1443
2441
543
681
2255
3247
4136
1088
631
2632
2949
1409
3450
732
2526
2737
1722
1313
4160
2304
733
4599
860
4366
-858993460
626
583
2788
1500
4504
3022
4262

[Infarction]

Ah, I see it now. When I ran it with MAXSIZE of 20 on my machine that didn't come up. The problem is here:

void FillMainList(int list[])
{
  int temp, test;
  for (int i=0; i<MAXSIZE; i++)
  {
    temp = (rand() % 5000);
    test = LinearSearch(list, temp);
    if (test == -1) // if the new value isn't in the list
      list[i] = temp; // then save it
    // otherwise.... it'll skip this index and you'll have the uninitialized value
  }
}

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

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
}

[bling_bling_vr6]

Sure, I understand. I'm just trying to quickly generate some random numbers in an array, however to check if the number is in the array before adding another random number. That way i'll have a list of all random numbers.

[iamthwee]

Can't you just create an array of 5000 ints

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.

[vijayan121]

... but I'm stuck on how to avoid filling it with duplicate values. I'm assuming that i'll have to use either a linear or binary search function while filling the array...

1. you cannot do a binary search; the array is not ordered.
2. a linear search is possible, but it is not very efficient. filling up an array of size N would takeO(N*N)
3. the smart thing to do would be to avoid the search alltogether.

to choose N unique numbers out of M
a. choose the first with probability N/M
b. choose the next with probability (N-1)/(M-1) if the first was chosen, N/(M-1) if it was not.
c. and so on.
this would take linear time. O(M)

here is an example of how this could be implemented.

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <iterator>
using namespace std ;

void fill_with_unique_rand( int* array, int N, int min_value, int max_value )
{
  int available = max_value - min_value +1 ;
  int required = N ;

  for( int i=0 ; i<available ; ++i )
    if( ( rand() % (available-i) ) < required )  // we have to choose required 
                                 // out of the remaining (available-i)
    {
      --required ;
      array[required] = min_value + i ;
    }

  random_shuffle( array, array+N ) ;   // if needed
}

template< int N > inline void fill_array_with_unique_rand( int (&array)[N], 
                                           int min_value, int max_value )
{ fill_with_unique_rand( array, N, min_value, max_value ) ; }

int main()
{
  srand( unsigned( time(0)) ) ;

  int a[10] ;  fill_array_with_unique_rand( a, 101, 200 ) ;
  copy( a, a+sizeof(a)/sizeof(*a), ostream_iterator<int>(cout," ") ) ; 
  cout << '\n' ;

  int b[20] ;  fill_array_with_unique_rand( b, 20, 40 ) ;
  copy( b, b+sizeof(b)/sizeof(*b), ostream_iterator<int>(cout," ") ) ; 
  cout << '\n' ;
}

[bling_bling_vr6]

Holy Schneikes!

That's it!!! Thanks a million infarction!

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
}

[iamthwee]

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

[vijayan121]

Can't you just create an array of 5000 ints

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.

[Infarction]

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 :icon_wink:

[iamthwee]

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

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

[bling_bling_vr6]

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

[~s.o.s~]

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

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
}

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

;)

[loveloic]

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!

[vijayan121]

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

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

[invisal]

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.

___  ___  ___  ___  ___  ___   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.

[sarehu]

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.