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