代码之家 › 专栏 › 技术社区 › Adam Maras

验证Knuth Shuffle算法是否尽可能无偏

knuth random shuffle algorithm c++

Adam Maras · 技术社区 · 16 年前

我正在执行 Knuth shuffle 对于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 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 );
}

5 回复 | 直到 11 年前

dsimcha 16 年前

好吧,作为黑盒测试,你可以做的一件事是取一些相对较小的数组大小,对其执行大量的无序排列,计算你观察每个排列的次数,然后执行 Pearson's Chi-square 测试结果是否均匀分布在置换空间上。

另一方面,只要指数来自的随机数生成器是无偏的,那么Knuth Shuffle(又称Fisher Yates Shuffle)就被证明是无偏的。

Svante 16 年前

如果我看对了,你的 random::get (max) 不包括 max .

这条线:

draw_t push_index = random::get( pull_index );

然后一个错误产生一个“经典”关闭,作为 pull_index 和 push_index 错误地永远不会是一样的。这就产生了一种微妙的偏见,你永远无法在洗牌前得到一个物品。在一个极端的例子中,这个“无序播放”下的两个项目列表总是相反的。

Robert Harvey 16 年前

看看Jeff Atwood的这篇文章:

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

参见:

纳威的危险
http://www.codinghorror.com/blog/archives/001015.html

Nick Johnson 16 年前

Knuth洗牌本身是无偏的:只有一系列的操作产生了每个可能的洗牌。然而,您的prng不太可能有足够的状态位来表示每一个可能的随机播放,所以真正的问题是,您的prng是否“足够随机”,与它将实际产生的随机播放集有关,以及您的播种策略是否足够安全。

只有你才能决定这一点,因为这取决于随机性不够强的洗牌的后果。例如,如果您处理的是真正的钱,我建议切换到加密安全的prng,并改进您的播种策略。虽然大多数内置的prng生成了很好的随机性,但它们也很容易进行反向工程,并且不带参数调用seed()很可能基于当前时间进行种子设定,这很容易预测。

Adolfo 11 年前

#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].
*/
}