c++ - 验证 Knuth 洗牌算法是否尽可能公正

Question

我正在实现 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;
}

我使用的随机函数已经过修改以消除 modulo bias . 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 );
}

Answer 1

好吧，作为黑盒测试，您可以做的一件事是采用一些相对较小的数组大小，对其执行大量洗牌，计算观察每个排列的次数，然后执行 Pearson's Chi-square测试以确定结果是否均匀分布在排列空间上。

另一方面，Knuth 洗牌，又名 Fisher-Yates 洗牌，被证明是无偏的，只要索引来自的随机数生成器是无偏的。