Generating small range of different random numbers?

Question

I am trying to generate a short range of (about 20) different / unique random numbers.

Here is what I have now:

unique_random.h:

#ifndef UNIQUE_RANDOM_H
#define UNIQUE_RANDOM_H

// generates a pseudo-random number in [min, max]
int random_number (unsigned int min, unsigned int max) {
    static bool seed_initialized = false;

    if (!seed_initialized) {
        seed_initialized = true;
        srand((unsigned int) time(NULL));
    }

    return rand() % (max - min + 1) + min; 
} 

// generates a random number different from the previously generated
int random_number_without_these (int min, int max, std::set<int>& generated) {
    int res = random_number (min, max);

    // if res one of the previous, generate again
    while (s.find(res) != s.end()) {
        res = random_number (min, max);
    }

    return res;
}

#endif

then the above functions would be called like so:

main.cpp:

#include <iostream>
#include <time.h>
#include <set>

#include "unique_random.h" 

int main() {

    std::set<int> already_generated;

    for (auto i = 0; i < 20; ++i) {

        int rand =  random_number_without_these(1,20, already_generated);
        already_generated.insert(rand);
    }

}

where the expected result is that there have been generated 20 consecutively unique values. What I have written now needs two functions, random_number_without_these(), random_number() and a container, set<int>, in order to work, that is why I am wondering:

Is there an easier way to generate short range of unique random numbers, possibly along the lines of the existing code?

Answer 1

Using std::set and e.g. std::uniform_int_distribution it's actually very easy:

#include <iostream>
#include <set>
#include <random>

std::set<int> generate_numbers(const int min, const int max, const int count)
{
    std::set<int> numbers;
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(min, max);

    while (numbers.size() < count)
    {
        numbers.insert(dis(gen));
    }

    return numbers;
}

int main()
{
    auto numbers = generate_numbers(1, 20, 20);
    for (auto const v : numbers)
    {
        std::cout << v << ' ';
    }
    std::cout << '\n';
}

I just don't see the sense in using std::set since that will keep all the values sorted, and you could just use a simple loop to generate the numbers, or std::iota. Using std::unordered_set I can see the point though.

Answer 2

I'd like to suggest this alternative function. It's basically the random_sample_n algorithm from the original SGI standard template library. It produces the numbers in order with uniform probability.

#include <algorithm>
#include <iostream>
#include <vector>

int random_number(int N) // random value in [0, N)
{
    static std::random_device seed;
    static std::mt19937 eng(seed());
    std::uniform_int_distribution<> dist(0, N - 1);
    return dist(eng);
}

std::vector<int> random_sample(int first, int last, int n)
{
    std::vector<int> numbers;
    int remaining = last - first + 1;
    int m = std::min(n, remaining);
    while (m > 0) {
        if (random_number(remaining) < m) {
            numbers.push_back(first);
            --m;
        }
        --remaining;
        ++first;
    }
    return numbers;
}

int main()
{
    auto numbers = random_sample(1, 100, 20);
    for (int value : numbers) {
        std::cout << value << " ";
    }
    std::cout << '\n';
}

Live demo on ideone.com

Answer 3

As for the record the below is a more-or-less faithful implementation of Fisher-Yates-Knuth-Durstenfeld that does not create an explicit representation of the source set.

The general idea of FYKD is to sample uniformly from a sequence. The selected element is put at the end of the sequence and the sampling continues for the sequence minus the last element. Rinse and repeat until you have enough numbers.

It is possible to emulate this behavior for sequences with an indexable generator without having to create the sequence in memory.

std::set<long>
rand_unique(const unsigned n, const long max)
{
    std::set<long> selected;

    if (max < 0l) {
        throw std::range_error("max must be >= 0");
    }

    if (n > max) {
        throw std::range_error("too many random numbers requested");
    }

    while (selected.size() < n) {
        long rnd = random() % (max - (long)selected.size());
        if (selected.empty()) {
            /* first number, may even be outside the loop */
            selected.insert(rnd);
        } else {        
            auto it = selected.lower_bound(rnd);
            /* how many numbers are before this one? */
            const long delta = (long)std::distance(selected.begin(), it);
            /**
             * all numbers before the current one have been struck,
             * so shift accordingly by delta
             **/
            rnd += delta;
            /* still a collision? skip over those until a miss */
            while (selected.find(rnd) != selected.end()) {
                rnd += 1l;
            }
            assert(rnd >= 0);
            assert(rnd < max);
            selected.insert(rnd);
        }
    }

    return selected;
}

This one has the nice feature that it terminates even with n == max (in O(mn)), i.e. rand_unique(1000, 1000) actually works without requiring monte carlo exponential time.

Since this is a little hard to get right, feel free to point out any remaining problems.

Answer 4

Of course. If (max - min) small to:

#include <iostream>
#include <string>
#include <vector>

std::vector<int> GenUnique(int min, int max, int count) {
  std::vector<int> numbers(max - min + 1), result(count);
  for (int i = 0; i < max - min + 1; ++i) {
    numbers[i] = i + min;
  }
  for (int i = 0; i < count; ++i) {
    int next_index = rand() % (numbers.size());
    result[i] = numbers[next_index];
    numbers[next_index] = numbers.back();
    numbers.pop_back();
  }
  return result;
}

int main()
{
    const auto seq = GenUnique(1, 20, 20);
    for (int elem : seq) {
      std::cout << elem << " ";
    }
    std::cout << std::endl;
}

Possible output:

4 16 10 1 2 11 15 20 18 19 3 5 12 9 6 14 17 13 8 7