Hi, Thanks for the response! On Wed, Jan 19, 2011 at 8:30 PM, Steven Watanabe <watanabesj@gmail.com> 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/