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?

Once you test it out, could you please post the correct code, for posterity? Thanks — Robert Gould, Sep 29 '08 at 03:39
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). — C. K. Young, Sep 29 '08 at 03:43

score 13 · Answer 1 · answered Sep 29 '08 at 03:42

13

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

answered Sep 29 '08 at 03:42

C. K. Young

219,335
46
382
435

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". – C. K. Young Sep 29 '08 at 03:46
Out of curiosity what benefit does inheriting from unary_function give? It's obvious from operator() what the input and output are... – Greg Rogers Sep 29 '08 at 03:50
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.... – C. K. Young Sep 29 '08 at 03:52
2

I can't find an online article, however, in Effective STL, Item 40 ("Make functor classes adaptable") talks about this. – C. K. Young Sep 29 '08 at 04:11
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 – Evan Teran Sep 29 '08 at 04:56

score 11 · Accepted Answer · answered Sep 29 '08 at 03:29

11

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.

answered Sep 29 '08 at 03:29

coppro

14,338
5
58
73

1

While you're moving the struct out to global level, feel free to also make it inherit from std::unary_function too. :-) – C. K. Young Sep 29 '08 at 03:38

score 5 · Answer 3 · edited Apr 20 '12 at 05:56

5

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

edited Apr 20 '12 at 05:56

user1202136

11,171
4
41
62

answered Mar 16 '10 at 19:55

baol

4,362
34
44

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()`. – Spire Nov 04 '11 at 23:07
@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. – baol Nov 12 '11 at 13:30

score 1 · Answer 4 · answered Feb 27 '14 at 02:25

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

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

4 Answers4

Linked