I'm implementing a Knuth shuffle for a C++ project I'm working on. I'm trying to get the most unbiased results from my shuffle (and I'm not an expert on (pseudo)random number generation). I just want to make sure this is the most unbiased shuffle implementation.
draw_t
is a byte type (typedef
'd to unsigned char
). items
is the count of items in the list. I've included the code for random::get( draw_t max )
below.
for( draw_t pull_index = (items - 1); pull_index > 1; pull_index-- )
{
draw_t push_index = random::get( pull_index );
draw_t push_item = this->_list[push_index];
draw_t pull_item = this->_list[pull_index];
this->_list[push_index] = pull_item;
this->_list[pull_index] = push_item;
}
The random function I'm using has been modified to eliminate modulo bias. RAND_MAX
is assigned to random::_internal_max
.
draw_t random::get( draw_t max )
{
if( random::_is_seeded == false )
{
random::seed( );
}
int rand_value = random::_internal_max;
int max_rand_value = random::_internal_max - ( max - ( random::_internal_max % max ) );
do
{
rand_value = ::rand( );
} while( rand_value >= max_rand_value );
return static_cast< draw_t >( rand_value % max );
}