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

Question

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?

Retina

Once you test it out, could you please post the correct code, for posterity? Thanks – Interplanetary

Greg: I've reverted your change. You never have to escape HTML characters in your code, if you're willing to use Markdown code blocks (indent each line 4 spaces). – Deflected

Just highlight the code, and click the "010 101" button. – Deflected

Robert: stackoverflow.com/questions/147391#147438 – Deflected

Answer 1

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.

Remanence

While you're moving the struct out to global level, feel free to also make it inherit from std::unary_function too. :-) – Deflected

Answer 2

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);
}

Deflected

Incidentally, this is not how I format code (I prefer "foo& bar", not "foo &bar"), but I thought I should leave it alone, just for people who think that such edits "might make a difference". – Deflected

Out of curiosity what benefit does inheriting from unary_function give? It's obvious from operator() what the input and output are... – Retina

It makes the functors more composable. i.e., it provides some typedefs that make building other functors out of your functor easier. Let me hunt down a link for you.... – Deflected

I can't find an online article, however, in Effective STL, Item 40 ("Make functor classes adaptable") talks about this. – Deflected

Couldnt you have just used hist original bar and then passed std::ptr_fun(bar) to the std::random_shuffle, seems like a lot less typing to do the same thing :-P – Breaking

Answer 3

I'm using tr1 instead of boost::random here, but should not matter much.

The following is a bit tricky, but it works.

#include <algorithm>
#include <tr1/random>


std::tr1::mt19937 engine;
std::tr1::uniform_int<> unigen;
std::tr1::variate_generator<std::tr1::mt19937, 
                            std::tr1::uniform_int<> >gen(engine, unigen);
std::random_shuffle(vec.begin(), vec.end(), gen);

Shreveport

This doesn't actually work due to an off-by-one error. As written, gen generates integers from 0 through N instead of 0 through N - 1 as required by std::random_shuffle(). – Willywilly

@Spire: uniform_int::operator(engine, N) returns a number in [0,N) (i.e. between 0 and N-1). So this, albeit tricky, actually works. – Shreveport

Answer 4

I thought it was worth pointing out that this is now pretty straightforward in C++11 using only the standard library:

#include <random>
#include <algorithm>

std::random_device rd;
std::mt19937 randEng(rd());
std::shuffle(vec.begin(), vec.end(), randEng);

Pettigrew