Home > OS >  Replacing random_shuffle with shuffle: How to make a random number generator with a given distributi
Replacing random_shuffle with shuffle: How to make a random number generator with a given distributi

Time:03-30

I am moving from C 11 to C 17 and I have to replace random_shuffle with shuffle. But I am facing the following issue:

I need to shuffle the contents of a vector using a random number generator with a particular distribution. In my case this is a std::piecewise_linear_distribution.

But I don't know how to create a UniformRandomBitGenerator with a given distribution.

I tried (link to code)

    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};


    std::mt19937 gen(std::random_device());

    std::vector<double> i{0.0, 0.1, 1.0};
    std::vector<double> w{0.0, 0.9, 1.0};
    std::piecewise_linear_distribution distr(i.begin(), i.end(), w.begin());

    shuffle(v.begin(), v.end(), distr(gen)); // error: 'distr' is not a UniformRandomBitGenerator

But shuffle requires a generator as a 3rd argument. How can I make this generator have the distribution I want?

Most examples over the net, like this one, in cppreference.com present a generator, which feeds a random number into a distribution.

With random_shuffle I had to make a function object with the following operator():

// random function with desired PDF (and corresponding CDF)
//
struct MyRandomFunc {
  size_t operator() (size_t n)
  {
     double rand_num = rand()/RAND_MAX; // 0 <= rand_num <= 1
     double num = CDF(rand_num); // where 'CDF' = desired cumulative distribution function
     return num * n;    // 'num' is a random number with the desired PDF
  }
};


std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::random_shuffle(v.begin(), v.end(), MyRandomFunc());  // random func with desired pdf

CodePudding user response:

How can I make this generator have the distribution I want?

You don't. std::shuffle requires a uniform random bit generator because it is defined as follows:

Permutes the elements in the range [first, last) such that each possible permutation of those elements has equal probability of appearance.

Emphasis added.

What you want is to control the possibility of certain permutations. That's not what shuffle is for, so you're going to have to write the shuffling code yourself. Even if you gave it a class that implemented the interface of URBG, the fact that the bits it generates are non-uniform means that the result of calling the function will be undefined. It might do what you want, or it could do something entirely different.

  • Related