我正在实现一个Knuth shuffle,用于我正在开发的C++项目中。我试图从我的洗牌中获得最不偏倚的结果(我对(伪)随机数生成不是专家)。我只想确保这是最不偏倚的洗牌实现。
我正在使用的随机函数已被修改以消除模数偏差。
draw_t
是一个字节类型(typedef
为 unsigned char
)。 items
是列表中项目的数量。下面是random::get( draw_t max )
的代码。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;
}
我正在使用的随机函数已被修改以消除模数偏差。
RAND_MAX
被赋值给 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 );
}
random_shuffle
。以防你不知道。 - rlbond