Help needed filling array with unique random numbers

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

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

Help needed filling array with unique random numbers

 
0
  #1
Apr 15th, 2007
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.

  1. #include <iostream>
  2. #include <string>
  3. #include <cstdlib>
  4. #include <iomanip>
  5. using namespace std;
  6.  
  7. //Global constant declaration
  8. const int MAXSIZE = 200;
  9. const int SEED = 12;
  10.  
  11. //Function Prototypes
  12. void Seed();
  13. void FillMainList(int list[]);
  14. void PrintArray(const int list[]);
  15. int LinearSearch(const int list[], int value);
  16.  
  17. int main ()
  18. {
  19. int list[MAXSIZE];
  20. Seed();
  21. FillMainList(list);
  22. PrintArray(list);
  23. return 0;
  24. }
  25.  
  26. void Seed() //Set & Display the seed value
  27. {
  28. srand(SEED);
  29. }
  30.  
  31. void FillMainList(int list[])
  32. {
  33. int temp, test;
  34. for (int i=0; i<MAXSIZE; i++)
  35. {
  36. temp = (rand() % 5000);
  37. test = LinearSearch(list, temp);
  38. if (test == -1)
  39. list[i] = temp;
  40. }
  41. }
  42.  
  43. void PrintArray(const int list[])
  44. {
  45. for (int i=0; i<MAXSIZE; i++)
  46. {
  47. cout << setw(5) << list[i] << endl;
  48. }
  49. cout << endl;
  50. }
  51. int LinearSearch(const int list[], int value)
  52. {
  53. int index = 0;
  54. int position = -1;
  55. bool found = false;
  56.  
  57. while (index < MAXSIZE && !found)
  58. {
  59. if (list[index] == value)
  60. {
  61. found = true;
  62. position = index;
  63. }
  64. index++;
  65. }
  66. return position;
  67. }
Reply With Quote Quick reply to this message  
Join Date: May 2006
Posts: 1,580
Reputation: Infarction has a spectacular aura about Infarction has a spectacular aura about Infarction has a spectacular aura about 
Solved Threads: 52
Infarction's Avatar
Infarction Infarction is offline Offline
Battle Programmer

Re: Help needed filling array with unique random numbers

 
0
  #2
Apr 15th, 2007
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.
Reply With Quote Quick reply to this message  
Join Date: Jun 2006
Posts: 7,635
Reputation: ~s.o.s~ has much to be proud of ~s.o.s~ has much to be proud of ~s.o.s~ has much to be proud of ~s.o.s~ has much to be proud of ~s.o.s~ has much to be proud of ~s.o.s~ has much to be proud of ~s.o.s~ has much to be proud of ~s.o.s~ has much to be proud of ~s.o.s~ has much to be proud of 
Solved Threads: 469
Super Moderator
Featured Poster
~s.o.s~'s Avatar
~s.o.s~ ~s.o.s~ is offline Offline
Failure as a human

Re: Help needed filling array with unique random numbers

 
0
  #3
Apr 15th, 2007
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.
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
Reply With Quote Quick reply to this message  
Join Date: May 2006
Posts: 1,580
Reputation: Infarction has a spectacular aura about Infarction has a spectacular aura about Infarction has a spectacular aura about 
Solved Threads: 52
Infarction's Avatar
Infarction Infarction is offline Offline
Battle Programmer

Re: Help needed filling array with unique random numbers

 
0
  #4
Apr 15th, 2007
Originally Posted by ~s.o.s~ View Post
• You need to break out of the loop in your linear search if the required value is found.
He sets a boolean flag
Reply With Quote Quick reply to this message  
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

 
0
  #5
Apr 15th, 2007
Originally Posted by ~s.o.s~ View Post
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
Reply With Quote Quick reply to this message  
Join Date: May 2006
Posts: 1,580
Reputation: Infarction has a spectacular aura about Infarction has a spectacular aura about Infarction has a spectacular aura about 
Solved Threads: 52
Infarction's Avatar
Infarction Infarction is offline Offline
Battle Programmer

Re: Help needed filling array with unique random numbers

 
0
  #6
Apr 15th, 2007
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:
  1. void FillMainList(int list[])
  2. {
  3. int temp, test;
  4. for (int i=0; i<MAXSIZE; i++)
  5. {
  6. temp = (rand() % 5000);
  7. test = LinearSearch(list, temp);
  8. if (test == -1) // if the new value isn't in the list
  9. list[i] = temp; // then save it
  10. // otherwise.... it'll skip this index and you'll have the uninitialized value
  11. }
  12. }
To fix that, you should put the random generator in a loop and use the LinearSearch results as a loop condition:
  1. for(int i = 0; i < MAXSIZE; i++)
  2. {
  3. do {
  4. temp = rand() % 5000; // get random number
  5. } while (LinearSearch(list, temp) != -1); // repeat till it's unique
  6. list[i] = temp; // save it
  7. }
Last edited by Infarction; Apr 15th, 2007 at 5:29 pm.
Reply With Quote Quick reply to this message  
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

 
0
  #7
Apr 15th, 2007
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.
Reply With Quote Quick reply to this message  
Join Date: Aug 2005
Posts: 5,273
Reputation: iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold 
Solved Threads: 378
Featured Poster
iamthwee's Avatar
iamthwee iamthwee is offline Offline
Posting Expert

Re: Help needed filling array with unique random numbers

 
0
  #8
Apr 15th, 2007
Can't you just create an array of 5000 ints

  1. for (int i =0; i< 5000; i++ )
  2. {
  3. array[i] =i;
  4. }

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.
*Voted best profile in the world*
Reply With Quote Quick reply to this message  
Join Date: Dec 2006
Posts: 1,089
Reputation: vijayan121 is a name known to all vijayan121 is a name known to all vijayan121 is a name known to all vijayan121 is a name known to all vijayan121 is a name known to all 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

 
0
  #9
Apr 15th, 2007
Originally Posted by bling_bling_vr6 View Post
... 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.
  1. #include <iostream>
  2. #include <ctime>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <iterator>
  6. using namespace std ;
  7.  
  8. void fill_with_unique_rand( int* array, int N, int min_value, int max_value )
  9. {
  10. int available = max_value - min_value +1 ;
  11. int required = N ;
  12.  
  13. for( int i=0 ; i<available ; ++i )
  14. if( ( rand() % (available-i) ) < required ) // we have to choose required
  15. // out of the remaining (available-i)
  16. {
  17. --required ;
  18. array[required] = min_value + i ;
  19. }
  20.  
  21. random_shuffle( array, array+N ) ; // if needed
  22. }
  23.  
  24. template< int N > inline void fill_array_with_unique_rand( int (&array)[N],
  25. int min_value, int max_value )
  26. { fill_with_unique_rand( array, N, min_value, max_value ) ; }
  27.  
  28. int main()
  29. {
  30. srand( unsigned( time(0)) ) ;
  31.  
  32. int a[10] ; fill_array_with_unique_rand( a, 101, 200 ) ;
  33. copy( a, a+sizeof(a)/sizeof(*a), ostream_iterator<int>(cout," ") ) ;
  34. cout << '\n' ;
  35.  
  36. int b[20] ; fill_array_with_unique_rand( b, 20, 40 ) ;
  37. copy( b, b+sizeof(b)/sizeof(*b), ostream_iterator<int>(cout," ") ) ;
  38. cout << '\n' ;
  39. }
Last edited by vijayan121; Apr 15th, 2007 at 5:42 pm.
Reply With Quote Quick reply to this message  
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

 
0
  #10
Apr 15th, 2007
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
}
Reply With Quote Quick reply to this message  
Reply

This thread is more than three months old.
Perhaps start a new thread instead?
Message:



Similar Threads
Other Threads in the C++ Forum
Thread Tools Search this Thread



Tag cloud for C++
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC