Knuth Shuffleアルゴリズムが可能な限り公平であることを確認してください

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

質問

私はaを実装しています クヌースシャッフル 私が取り組んでいるC ++プロジェクトの場合。私はシャッフルから最も公平な結果を得ようとしています（そして、私は（擬似）乱数の生成の専門家ではありません）。これが最も公平なシャッフルの実装であることを確認したいだけです。

draw_t バイトタイプです（typedef'd to 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;
}

私が使用しているランダム関数は、除去するように変更されています モジュロバイアス. 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 );
}
役に立ちましたか？

解決

まあ、ブラックボックステストとしてできることの1つは、比較的小さな配列サイズを取得し、その上に多数のシャッフルを実行し、各順列を観察する回数を数えて、実行することです。 ピアソンのカイ二乗 結果が順列空間に均一に分布するかどうかを判断するためのテスト。

一方、Knuth Shuffle（別名Fisher-Jates Shuffle）は、インデックスが由来している乱数ジェネレーターが偏見がない限り、偏見がないことが証明されています。

他のヒント

私がそれを正しく見るなら、あなた random::get (max) 含まれていません max.

この行：

draw_t push_index = random::get( pull_index );

次に、あなたのように、「クラシック」オフ1つのエラーを生成します pull_index と push_index 誤って同じになることはありません。これにより、シャッフルの前にあったアイテムを持つことはできない微妙なバイアスが生成されます。極端な例では、この「シャッフル」の下にある2項目のリストは常に逆になります。

ジェフアトウッドのこの記事をご覧ください：

シャッフリング
http://www.codinghorror.com/blog/archives/001008.html

参照：

ナイベテの危険
http://www.codinghorror.com/blog/archives/001015.html

Knuth Shuffle自体は、公平ではないことが証明されています。それぞれの可能なシャッフルを生成する一連の操作が正確に存在します。 PRNGにはあらゆる可能なシャッフルを表現するのに十分な状態がある可能性は低いので、実際の問題は、PRNGが実際に生成するシャッフルのセットに関して「十分にランダム」であるかどうか、およびシード戦略が十分に安全であるかどうかです。

それは、十分にランダムではないシャッフルの結果に依存するため、これを決定することができます。たとえば、実際のお金を扱っている場合は、暗号化されたPRNGに切り替えて、シード戦略を改善することをお勧めします。 PRNGのほとんどは良好なランダム性を生成しますが、それらはまた非常に簡単にリバースエンジニアリングします。Seed（）を呼び出して、現在の時刻に基づいてシードが発生する可能性が高いため、予測が非常に簡単です。

#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