Re: [Boost-users] Random permutations using boost::random_number_generator and std::random_shuffle.

Subject: Re: [Boost-users] Random permutations using boost::random_number_generator and std::random_shuffle.
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2011-01-19 15:30:01

AMDG

On 1/19/2011 10:45 AM, Matthew Gwynne wrote:
> We need the ability to randomly permute some range, and we already
> have this functionality available in the computer algebra system
> Maxima. We use Maxima for numerous things, often implementing basic
> algorithms in it, then later writing more efficient versions in C++.
>
> The problem we have is that we'd like to be able to make sure that any
> function we write to randomly shuffle a range, matches up with the
> Maxima "random_permutation" function.
>
> We believe it uses the Mersenne twister (boost::mt19937) and Knuth
> shuffle algorithms, and so we thought to implement these in C++ using
> boost::uniform_distribution, boost:variate_generator etc.
>

If you want to duplicate the behavior exactly,
you may have to write it yourself, except for
mt19937 which has precisely specified behavior.

> However, we have two questions (open problems):
>
> 1) How does boost::variate_generator interact with mt19937, and the
> distribution? Is this documented somewhere?
>
> In the attached code, it seems we can construct
> boost::uniform_distribution with any maximum value, and still the
> number generator returns values outside of that range? Is this really
> right?
>

Yes.  You don't need to use uniform_int with
random_number_generator.  You can plug mt19937
directly into random_number_generator.

> 2) What algorithm does std::random_shuffle implement? (Not boost
> related specifically but hopefully someone will know)
>

I suggest that you read the code.  It's not very complex.

> Is this defined by the C++ standard?

No it isn't.

> It doesn't seem to be the simple
> Knuth shuffle algorithm (starting from top of range to bottom or vice
> versa) as we implement in the attached code. If anyone could point me
> in the right direction, I'd very much appreciate it.
>

In Christ,
Steven Watanabe