Generating m distinct random numbers in the range [0..n-1]

user_469935 0
Viewed 33825

I have two methods of generating m distinct random numbers in the range [0..n-1]

Method 1:

//C++-ish pseudocode
int result[m];
for(i = 0; i < m; ++i)
{
   int r;
   do
   {
      r = rand()%n;
   }while(r is found in result array at indices from 0 to i)
   result[i] = r;   
}

Method 2:

//C++-ish pseudocode
int arr[n];
for(int i = 0; i < n; ++i)
    arr[i] = i;
random_shuffle(arr, arr+n);
result = first m elements in arr;

The first method is more efficient when n is much larger than m, whereas the second is more efficient otherwise. But "much larger" isn't that strict a notion, is it? :)

Question: What formula of n and m should I use to determine whether method1 or method2 will be more efficient? (in terms of mathematical expectation of the running time)

random algorithm c++ performance
11 Answers

What about using set instead of array, i think it is much easier than array 

set<int> Numbers;
while (Numbers.size() < m) {
   Numbers.insert(rand() % n);
}
user_71526930

There was suggested Fisher-Yates shuffle. Don't know if the next code generates equally distributed integers, but it is at least compact and one-pass:

std::random_device rd;
std::mt19937 g(rd());
for (size_type i = 1; i < std::size(v); ++i) {
    v[i] = std::exchange(v[g() % i], i);
}
user_14309270

I don't advise this method but it works

#include <iostream>
#include <random>
#include <ctime>

using namespace std;

int randArray[26];
int index = 0;

bool unique(int rand) {

    for (int i = 0; i < index; i++)
        if (rand == randArray[i])
            return false;
    index++;
    return true;
}


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

    for (int i = 1; i < 26; i++)
        randArray[i] = -1;

    for (int i = 0; i < 26; i++) {

        randArray[i] = rand() % 26;

        while (!unique(randArray[i])) {
            randArray[i] = rand() % 26;
        }
    }

    for (int i = 0; i < 26; i++) {
        cout << randArray[i] << " ";
    }

    cout << "\n" << index << endl;


    return 0;
}
user_71085220
Related