Ad:

C++ Discussion Thread
Unsolved
Views: 18181

Page 1
2
3
4
Next

You are currently viewing page 1 of this multi-page discussion thread

Apr 15th, 2007

Help needed filling array with unique random numbers

Expand Post »

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.

C++ Syntax (Toggle Plain Text)
#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;
}
#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;
}

Similar Threads

Random Numbers on button in Java
Help with Java programming for lottery in Java

bling_bling_vr6

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

7 posts
since Apr 2007

Permalink

Apr 15th, 2007

Re: Help needed filling array with unique random numbers

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.

Infarction

Reputation Points: 683

Solved Threads: 53

Posting Virtuoso

Offline

1,580 posts
since May 2006

Permalink

Apr 15th, 2007

Re: Help needed filling array with unique random numbers

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.

Last edited by ~s.o.s~; Apr 15th, 2007 at 3:28 pm.

~s.o.s~

Super Moderator

Featured Poster

Reputation Points: 3233

Solved Threads: 719

Failure as a human

Offline

8,871 posts
since Jun 2006

Permalink

Apr 15th, 2007

Re: Help needed filling array with unique random numbers

Click to Expand / Collapse Quote originally posted by ~s.o.s~ ...

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

He sets a boolean flag

Infarction

Reputation Points: 683

Solved Threads: 53

Posting Virtuoso

Offline

1,580 posts
since May 2006

Permalink

Apr 15th, 2007

Re: Help needed filling array with unique random numbers

Click to Expand / Collapse Quote originally posted by ~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.

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

bling_bling_vr6

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

7 posts
since Apr 2007

Permalink

Apr 15th, 2007

Re: Help needed filling array with unique random numbers

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:

C++ Syntax (Toggle Plain Text)
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
  }
}
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:

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
}

Last edited by Infarction; Apr 15th, 2007 at 5:29 pm.

Infarction

Reputation Points: 683

Solved Threads: 53

Posting Virtuoso

Offline

1,580 posts
since May 2006

Permalink

Apr 15th, 2007

Re: Help needed filling array with unique random numbers

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.

bling_bling_vr6

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

7 posts
since Apr 2007

Permalink

Apr 15th, 2007

Re: Help needed filling array with unique random numbers

Can't you just create an array of 5000 ints

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.

iamthwee

Featured Poster

Reputation Points: 1536

Solved Threads: 431

Posting Expert

Offline

5,865 posts
since Aug 2005

Permalink

Apr 15th, 2007

Re: Help needed filling array with unique random numbers

Click to Expand / Collapse Quote originally posted by bling_bling_vr6 ...

... 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 take O(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.

C++ Syntax (Toggle Plain Text)
#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' ;
}
#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' ;
}

Last edited by vijayan121; Apr 15th, 2007 at 5:42 pm.

vijayan121

Reputation Points: 1159

Solved Threads: 285

Posting Virtuoso

Offline

1,606 posts
since Dec 2006

Permalink

Apr 15th, 2007

Re: Help needed filling array with unique random numbers

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
}

bling_bling_vr6

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

7 posts
since Apr 2007

Page 1
2
3
4
Next

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: virtual class with friend functions

Next Thread in C++ Forum Timeline: Simple Varifacation please

DaniWeb Message

Cancel Changes

User Name
Password