How to produce normal distribution without duplicates in C++?

Question

I am trying to find a fast way to produce random float numbers between 0 and 1 normally distributed but from the implementations that I have seen its all about random numbers meaning that there are possible duplicate values.

My restriction is that I want to produce millions of numbers, lets say 8M or 16M etc and avoid duplicate numbers.

The C++ std::normal_distribution is a random generator as well.

Is there any implementation of what I seek or do I have to check every time if the produced value already exists (something that would really slow down down the whole program as we are speaking about millions of numbers).

I know that normal distribution implies duplicates that is why I have opened this question.

Answer 1

I'd solve this problem using a std::unordered_set to check for already generated numbers. This has expected constant time for both checking and inserting, since it's based on a hash table; summing up to a linear time complexity in the number of numbers to be generated N.

Generic solution which works with any distribution:

template <typename T, typename Dist, typename Gen>
std::unordered_set<T> unique_generate(Dist &&dist, Gen &&generator, size_t N)
{
    std::unordered_set<T> generated;
    while (generated.size() < N)
        generated.insert(dist(generator));
    return generated;
}

Usage with normal_distribution:

std::random_device rd;
std::mt19937 gen(rd());
std::normal_distribution<double> d(meanValue, stdDevValue);
int N = 1000000;

auto myNumbers = unique_generate<double>(d, gen, N);

To also enforce the numbers to be in the interval [0, 1], you can wrap the distribution object using a generic wrapper class ("separation of concerns": don't mix the unique generation with the distribution clamping).

A possible (possibly slow*) implementation throws away generated numbers which are out of bounds:

template<typename Dist, typename T>
class ClampedDistribution {
    Dist dist;
    T min, max;
public:
    ClampedDistribution(Dist dist, T min, T max) :
        dist(dist), min(min), max(max)
    {}

    template <typename Gen>
    auto operator()(const Gen & generator) -> decltype(dist(generator)) {
        auto value = dist(generator);
        while (value > max || value < min)
            value = dist(generator);
        return value;
    }
};

// type-deducing function:
template<typename Dist, typename T>
ClampedDistribution<Dist,T> clamped(Dist dist, T min, T max) {
    return ClampedDistribution<Dist,T>(dist, min, max);
}

Usage:

// (from above)
std::normal_distribution<double> d(meanValue, stdDevValue);

// clamp it:
auto clamped_dist = clamped(d, 0.0, 1.0);

// and pass this to unique_generate:
auto myNumbers = unique_generate(clamped_dist, gen, N);

---

*) It's slow if you choose a high standard deviation for your normal distribution. It's reasonably fast for small deviations though, as the numbers chosen by the normal distribution are more likely to be in the range already.

Answer 2

My math is a little rusty so I hope I didn't make any horrible mistakes.

The approach I took was to increment a variable between -1 and +1. I then calculate the normal distribution curve for each value, comparing it against a random number between [0,1] to decide whether or not to include it in the output. Thus the closer we get to the mean the more values should get included - no duplicates.

After generating the numbers and storing them in a std::vector I perform a random shuffle:

#include <cmath>
#include <random>
#include <iostream>
#include <algorithm>

double normal(double x, const double mu, const double sigma)
{
    double fac = 1 / (sigma * sqrt(2 * M_PI));
    double exp = pow(x - mu, 2) / (2 * sigma * sigma);
    return fac * pow(M_E, -exp);
}

// res = resolution (distance between samples) [res < 1]
std::vector<double> generate(double res, const double mu, const double sigma)
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_real_distribution<> dis(0, 1);

    std::vector<double> values;

    for(double x = -1; x < 1; x += res)
        if(dis(gen) < normal(x, mu, sigma))
            values.push_back(x);

    std::shuffle(values.begin(), values.end(), gen);

    return values;
}

int main()
{
    std::vector<double> values = generate(0.000001, 0, 1);

    std::cout << values.size() << '\n';
    for(auto v: values)
        std::cout << v << '\n';
}

EDIT: Improved version:

Added parametrization of the range. Improved yield.

// normal probability density function
double normal_pdf(const double x, const double mu, const double sigma)
{
    double fac = 1 / (sigma * sqrt(2 * M_PI));
    double exp = pow(x - mu, 2) / (2 * sigma * sigma);
    return fac * pow(M_E, -exp);
}

/**
 * Randomly generate unique values between [i0, i1)
 * with a normal distribution.
 *
 * @param i0 The lower, inclusive bound of the range
 * of the generated values.
 *
 * @param i1 The upper, exclusive bound of the range
 * of the generated values.
 *
 * @param res The resolution. The size between samples when
 * calculating the values (< 0).
 *
 * @param mu The mean value of the distribution PDF
 *
 * @param sigma The Standard Deviation of the PDF.
 *
 * @return A std::vector<double> containing thegenerated
 * values.
 */
std::vector<double> generate(const double i0, const double i1
    , const double res, const double mu, const double sigma)
{
    std::random_device rd;
    std::mt19937 gen(rd());

    std::vector<double> values;

    double maximum = normal_pdf(mu, mu, sigma);

    std::uniform_real_distribution<> dis(0, maximum);

    for(double x = i0; x < i1; x += res)
        if(dis(gen) < normal_pdf(x, mu, sigma))
            values.push_back(x);

    std::shuffle(values.begin(), values.end(), gen);

    return values;
}

int main()
{
    std::vector<double> values = generate(0, 1, 0.01, 0.5, 1);

    std::cout << values.size() << '\n';
    for(auto v : values)
        std::cout << v << '\n';
}

Answer 3

Mechanical answer (not questioning "normal - without duplicate") below:

using gen = std::normal_distribution<long>(_1, _2);
std::set<long> data; // if you want to use double you'll need to customize the comparator
std::generate(std::inserter(data, data.end()), _3, gen);

Answer 4

Normal distribution means that you may have many duplicates near the math expectation value. Your constraint make sense when you deal with even distribution.