RSS Forums RSS
Please support our C++ advertiser: Programming Forums

Help needed filling array with unique random numbers

Join Date: Dec 2006
Location: india
Posts: 1,087
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 
Rep Power: 9
Solved Threads: 163
vijayan121 vijayan121 is offline Offline
Veteran Poster

Re: Help needed filling array with unique random numbers

  #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.
#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.
Reply With Quote  
Forums | Blogs | Tutorials | Code Snippets | Whitepapers | RSS Feeds | Advertising
All times are GMT -4. The time now is 5:47 am.
Newsletter Archive - Sitemap - Privacy Statement - Acceptable Use Policy - Contact Us
Forum system based on vBulletin Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
©2003 - 2008 DaniWeb® LLC