我采取一个克努特洗牌的C ++项目我的工作。我想从我的洗牌最公正的结果（和我不是（伪）随机数生成方面的专家）。我只是想确认这是最公正的洗牌实施。

draw_t 是一个字节型（的typedef 'D为无符号的字符）。 项目在列表中的项目数。我已经包含了$ C $下随机::得到（draw_t最大）下面。

 的（draw_t pull_index =（项目 -  1）; pull_index大于1; pull_index--）
{
    draw_t push_index =随机::得到（pull_index）;

    draw_t push_item =这 - ＆GT; _list [push_index]
    draw_t pull_item =这 - ＆GT; _list [pull_index]

    这 - ＆GT; _list [push_index] = pull_item;
    这 - ＆GT; _list [pull_index] = push_item;
}
 

随机函数我使用的是已被修改，以消除模偏置 。 RAND_MAX 分配给随机:: _ internal_max 。

  draw_t随机::得到（draw_t最大值）
{
    如果（随机:: _ is_seeded ==假）
    {
        随机::种子（）;
    }

    INT rand_value =随机:: _ internal_max;
    INT max_rand_value =随机:: _ internal_max  - （最大值 - （随机:: _ internal_max％以下））;

    做
    {
        rand_value = ::兰特（）;
    }而（rand_value＆GT; = max_rand_value）;

    返回的static_cast＆LT; draw_t＆GT;（rand_value％以下）;
}
 

解决方案

嗯，有一件事你可以做一个黑箱测试是采取一些比较小的数组的大小，进行了大量的关于它的洗牌，算多少有时你看到每个排列，然后执行 Pearson的卡方测试，以确定是否结果均匀地分布在空间置换

在另一方面，在高德纳洗牌，AKA费雪耶茨洗牌，证明只要该指数都来自随机数发生器是公正是公正的。

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

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.

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.