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: Matthew Gwynne (mathew.gwynne_at_[hidden])
Date: 2011-01-21 16:57:17

Hi,

Thanks for the response!

On Wed, Jan 19, 2011 at 8:30 PM, Steven Watanabe <watanabesj_at_[hidden]> wrote:
> 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.

The problem we now have is that we don't know how the result of
mt19937 is being cast down into the number range we are asking for. As
far as I am aware, MT19937 only defines how to get a 32 bit integer,
not how to then scale that to say the range 1..10. Is it specified
clearly how boost::random_number_generator or
boost::uniform_distribution does this?

>
>> 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.

Thanks! Is the behaviour exactly the same? It seems so, but the
documentation seems to suggest using boost::uniform_distribution.

>
>> 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.

Ah yes! I see what you mean :) Thanks! That was very helpful, I
should've looked there first, but didn't have source immediately to
hand.

>
>> Is this defined by the C++ standard?
>
> No it isn't.

:(

Thanks again!

Matthew Gwynne
http://cs.swan.ac.uk/~csmg/