Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Using boost::random as the RNG for std::random_shuffle

I have a program that uses the mt19937 random number generator from boost::random. I need to do a random_shuffle and want the random numbers generated for this to be from this shared state so that they can be deterministic with respect to the mersenne twister's previously generated numbers.

I tried something like this:

void foo(std::vector<unsigned> &vec, boost::mt19937 &state)
{
    struct bar {
        boost::mt19937 &_state;
        unsigned operator()(unsigned i) {
            boost::uniform_int<> rng(0, i - 1);
            return rng(_state);
        }
        bar(boost::mt19937 &state) : _state(state) {}
    } rand(state);

    std::random_shuffle(vec.begin(), vec.end(), rand);
}

But i get a template error calling random_shuffle with rand. However this works:

unsigned bar(unsigned i)
{
    boost::mt19937 no_state;
    boost::uniform_int<> rng(0, i - 1);
    return rng(no_state);
}
void foo(std::vector<unsigned> &vec, boost::mt19937 &state)
{
    std::random_shuffle(vec.begin(), vec.end(), bar);
}

Probably because it is an actual function call. But obviously this doesn't keep the state from the original mersenne twister. What gives? Is there any way to do what I'm trying to do without global variables?

like image 248
Greg Rogers Avatar asked Sep 29 '08 03:09

Greg Rogers


People also ask

Why was std :: Random_shuffle removed?

The reason for removing std::random_shuffle in C++17 is that the iterator-only version usually depends on std::rand, which is now also discussed for deprecation. (std::rand should be replaced with the classes of the <random> header, as std::rand is considered harmful.)

How do you randomly shuffle a vector?

A vector shuffle can be done in the Fisher-Yates shuffle algorithm. In this algorithm, a linear scan of a vector is done and then swap each element with a random element among all the remaining element, including the element itself.

What is random shuffle in C++?

Rearranges the elements in the range [first, last) randomly, using g as uniform random number generator.


2 Answers

In the comments, Robert Gould asked for a working version for posterity:

#include <algorithm>
#include <functional>
#include <vector>
#include <boost/random.hpp>

struct bar : std::unary_function<unsigned, unsigned> {
    boost::mt19937 &_state;
    unsigned operator()(unsigned i) {
        boost::uniform_int<> rng(0, i - 1);
        return rng(_state);
    }
    bar(boost::mt19937 &state) : _state(state) {}
};

void foo(std::vector<unsigned> &vec, boost::mt19937 &state)
{
    bar rand(state);
    std::random_shuffle(vec.begin(), vec.end(), rand);
}
like image 107
Chris Jester-Young Avatar answered Oct 05 '22 03:10

Chris Jester-Young


In C++03, you cannot instantiate a template based on a function-local type. If you move the rand class out of the function, it should work fine (disclaimer: not tested, there could be other sinister bugs).

This requirement has been relaxed in C++0x, but I don't know whether the change has been implemented in GCC's C++0x mode yet, and I would be highly surprised to find it present in any other compiler.

like image 43
coppro Avatar answered Oct 05 '22 02:10

coppro