验证Knuth shuffle算法是尽可能无偏差的

本文介绍了验证Knuth shuffle算法是尽可能无偏差的的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在为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.