Pseudocode for storing unique random numbers in an array

Question

Okay guys, I'm an idiot apparently, and can't figure out this simple simple problem.

The rest of my code isn't worth anything, so I'll just post relevant code. I already know WHY it's broken, but I don't know HOW to fix it. I'm really just looking more for pseudocode to give me a starting point.

What I'm trying to do is make an array called "temp", and store in each of its 5 indices a unique random number (these numbers will be used later as indices to a different array). It's not simply a matter of initializing it from 1 to 5 and using a shuffle though because the random numbers can be up to the number of vertices in my graph, numVertices.

int place = -1;

int temp[5] = {-1};
for(int i = 0; i < 5 || i < numVertices; i++){
    do{
        place = rand();
        place = (double)place / RAND_MAX * numVertices;
        temp[i] = place;
    } while(place == temp[0] or
          place == temp[1] or
          place == temp[2] or
          place == temp[3] or 
          place == temp[4]); ......`

Clearly, my code gets stuck in an infinite loop because it compares place (the random index I'm storing into a different array) to temp[i], and after it performs the operation it will always equal temp[i]. What I'm TRYING to do is compare it to the others and go "If it matches one of the stored numbers already, randomize place again until it doesn't match, then store it in the next slot in temp." However, I can't for my life think of how to do this..

Answer 1

It helps if you break things down into simple pieces. It looks like you're using the C language here. So, first a definition for number of vertices:

#define NUM_VERTICES 1000

Then a trivial function to generate a random number x such that lower_bound <= x < upper_bound:

int next_random( int inclusive_lower_bound , int exclusive_upper_bound )
{
  int n = exclusive_upper_bound - inclusive_lower_bound ; // size of desired domain
  int r = rand() % n ;                                    // 0 <= r < n
  int x = inclusive_lower_bound + r ;                     // min <= x < max
  return x ;
}

Then a trivial function to see if your buffer already contains a value:

int contains( int x, int *p, int limit)
{
  int j = 0 ;
  while ( j < limit && p[j] != x )
  {
    ++j;
  }
  return (j < limit ? 1 : 0);
}

Then a trivial function to generate the next unique value in the domain:

int next_unique_random( int* p, int limit, int upper_bound )
{
  int x , j ;
  do
  {
    x = next_random( 0 , upper_bound ) ;
  } while ( contains(x,p,limit) ) ;
  return x ;
}

Finally, we can put it all together:

int main()
{
  int temp[5] = { 0, 0, 0, 0 } ;
  int i = 0;

  for (i = 0; i < 5; ++i )
  {
    temp[i] = next_unique_random( temp , i , NUM_VERTICES ) ;
  }

  return 0;
}

Easy!

Answer 2

Instead of writing a huge conditional, write another loop.

...
while (true) {
    ...
    bool tryAgain = false;
    for(int j = 0; j < i; j++) {
        if (temp[j] == temp[i]) 
            tryAgain = true;
    }
    if (!tryAgain)
         break;
}

But if I were writing this in Java, I would use a HashSet to store the numbers and use its efficient contains method to tell me if i've used the number already. Although, because the array is so small (5 elements), the above code should be pretty fast regardless.

Answer 3

#include <array>
#include <cstdlib>
#include <ctime>
#include <set>
#include <iostream>

int main()
{    
  srand(time(NULL));

  std::array<int, 5> a;
  std::set<int> s;
  int r;

  for(size_t i = 0; i < a.size(); ++i)
  {
    do 
    {
      r = rand();
    } while(s.find(r) != s.end());

    a[i] = r;
    s.insert(r);
  }

  for(const auto& i: a)
    std::cout << i << std::endl;

  return 0;
}

Answer 4

Edit, again : I just saw your comment :

'use strict'

var numVertices = 100,
    temp = [];

var RAND_MAX = 32767;

for(var i = 0; i < 5; i++){
    var place = parseInt(Math.random() * numVertices),  // C++ : rand() % numVertices
        valid = true;
    //place = place * numVertices;
    for(var x = 0; x < temp.length; x++) {
        if(temp[x] == place) {
            i--;
            valid = false;
            break
        }
    }
    if(valid) temp[i] = place;
}
console.log(temp);

You can't use == when comparing floats / doubles, here's the code to do it in Javascript, but it's simple enough to port :

*edit : * check What is the most effective way for float and double comparison? for more information about comparing floats.

'use strict'

var numVertices = 5,
    temp = [];

var RAND_MAX = 32767,
    EPSILON = 1.00000001

for(var i = 0; i < 5 || i < numVertices; i++){
    var place = Math.random(),
        valid = true;
    place = place / RAND_MAX * numVertices;
    for(var x = 0; x < temp.length; x++) {
        if(Math.abs(temp[x] - place) > EPSILON) { //Math.abs == fabs in C/C++
            i--;
            valid = false;
            break
        }
    }
    if(valid) temp[i] = place;
}
console.log(temp);