| | |
Help needed filling array with unique random numbers
Please support our C++ advertiser: Intel Parallel Studio Home
![]() |
•
•
Join Date: Apr 2007
Posts: 7
Reputation:
Solved Threads: 0
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; }
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.
- 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.
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.
• 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.
•
•
Join Date: Apr 2007
Posts: 7
Reputation:
Solved Threads: 0
•
•
•
•
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.
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
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:
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)
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 } }
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 }
Last edited by Infarction; Apr 15th, 2007 at 5:29 pm.
Can't you just create an array of 5000 ints
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.
C++ Syntax (Toggle Plain Text)
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.
*Voted best profile in the world*
•
•
Join Date: Dec 2006
Posts: 1,089
Reputation:
Solved Threads: 164
•
•
•
•
... 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...
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' ; }
Last edited by vijayan121; Apr 15th, 2007 at 5:42 pm.
![]() |
Similar Threads
Other Threads in the C++ Forum
- Previous Thread: virtual class with friend functions
- Next Thread: Simple Varifacation please
| Thread Tools | Search this Thread |
api array arrays based beginner binary bitmap c++ c/c++ calculator char class classes code compile compiler console conversion count delete deploy desktop directshow dll download dynamic dynamiccharacterarray encryption error file forms fstream function functions game getline givemetehcodez google graph gui homeworkhelp homeworkhelper iamthwee ifstream input int integer java lib linkedlist linker linux list loop looping loops map math matrix memory news node output parameter pointer problem program programming project proxy python read recursion recursive reference return rpg string strings struct temperature template templates test text text-file tree unix url variable vector video visual visualstudio win32 windows winsock word wordfrequency wxwidgets






