验证Knuth Shuffle算法尽可能公正

StackOverflow https://stackoverflow.com/questions/1685339

题

我正在实施 诺斯洗牌 对于我正在进行的C ++项目。我正在尝试从洗牌中获得最无偏见的结果（我不是（伪）随机数的专家）。我只想确保这是最公正的洗牌实现。

draw_t 是字节类型（typedef'd 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偏见. 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::get (max) 不包括 max.

这线：

draw_t push_index = random::get( pull_index );

然后产生一个“经典”的逐一错误，作为您的 pull_index 和 push_index 错误地永远不会相同。这会产生一个微妙的偏见，您永远无法在洗牌之前拥有物品。在一个极端的示例中，此“洗牌”下的两个项目列表总是会逆转。

看看杰夫·阿特伍德（Jeff Atwood）的这篇文章：

洗牌
http://www.codinghorror.com/blog/archives/001008.html

也可以看看：

天真的危险
http://www.codinghorror.com/blog/archives/001015.html

诺斯（Knuth）的洗牌本身是公正的：恰好存在一系列的操作，这些操作产生了每种可能的洗牌。但是，您的prng不太可能有足够的状态表达所有可能的洗牌，因此，真正的问题是，您的prng是否足够“随机” 。

只有您可以决定这一点，因为这取决于不够随机的混音的后果。例如，如果您要处理真实的钱，我建议您改用隐藏在密码上的PRNG并改善您的播种策略。尽管大多数内置的prng都会产生良好的随机性，但它们也很容易反向工程，并且在没有参数的情况下调用种子（）可能是根据当前时间播种的，这很容易预测。

#include <cstdlib> // srand() && rand()

/** Shufle the first 'dim' values in array 'V[]'.
    - Implements the Fisher–Yates_shuffle.
    - Uses the standard function 'rand()' for randomness.
    - Initialices the random sequence using 'seed'.
    - Uses 'dim' swaps.
    \see http://stackoverflow.com/questions/1685339/
    \see http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm
*/
template <class T>
void Fisher_Yates_shuffle( T* V, unsigned dim , unsigned seed ) {
    srand(seed);
    T temp;
    unsigned i,iPP;

    i   = dim-1;
    iPP = dim;
    while ( i>0 ) {
        unsigned j = rand() % iPP;
        if ( i!=j ) { // swap
            temp = V[i]; V[i] = V[j]; V[j] = temp;
        }
        iPP = i;
        --i;
    }
/*
    This implementation depends on the randomness of the random number
    generator used ['rand()' in this case].
*/
}
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top