验证Knuth shuffle算法是尽可能无偏差的 [英] Verify Knuth shuffle algorithm is as unbiased as possible

问题描述

我正在为C ++实施 Knuth shuffle 项目我正在工作。我试图从我的shuffle（我不是一个（伪）随机数生成的专家）得到最公正的结果。我只是想确保这是最公正的shuffle实现。

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 是一个字节类型c $ c> typedef 'd至 unsigned char ）。 项目是列表中项目的计数。我包括了 random :: get（draw_t max）的代码。

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;
}

我使用的随机函数已修改为消除 modulo bias 。 RAND_MAX 分配给 random :: _ internal_max 。

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 );
}

推荐答案

做一个黑盒测试是一些相对较小的数组大小，执行大量的shuffle上，计数你观察每次排列的次数，然后执行 Pearson's Chi-square 测试，以确定结果是否均匀分布在排列空间中。

Well, one thing you could do as a black-box test is take some relatively small array size, perform a large number of shuffles on it, count how many times you observe each permutation, and then perform Pearson's Chi-square test to determine whether the results are uniformly distributed over the permutation space.

另一方面，Knuth shuffle，即Fisher-Yates shuffle的AKA，被证明是无偏的，只要指数来自的随机数发生器是无偏的。

On the other hand, the Knuth shuffle, AKA the Fisher-Yates shuffle, is proven to be unbiased as long as the random number generator that the indices are coming from is unbiased.

这篇关于验证Knuth shuffle算法是尽可能无偏差的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！