4

私が取り組んでいる C++ プロジェクトにKnuth シャッフルを実装しています。私はシャッフルから最も偏りのない結果を得ようとしています (そして、私は (疑似) 乱数生成の専門家ではありません)。これが最も偏りのないシャッフルの実装であることを確認したいだけです。

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

5 に答える 5

8

ブラックボックステストとして実行できることの1つは、比較的小さな配列サイズを取得し、その配列に対して多数のシャッフルを実行し、各順列を観察する回数をカウントしてから、ピアソンのカイ2乗検定を実行して結果は、順列空間全体に均一に分散されます。

一方、クヌースシャッフル、別名フィッシャー-イェーツシャッフルは、インデックスの元となる乱数ジェネレーターがバイアスされていない限り、バイアスされていないことが証明されています。

于 2009-11-06T04:23:36.413 に答える
8

私がそれを正しく見れば、あなたにrandom::get (max)は含まれていませんmax。

この行：

draw_t push_index = random::get( pull_index );

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

于 2009-12-08T13:26:03.937 に答える
3

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

シャッフル
http://www.codinghorror.com/blog/archives/001008.html

参照：

ナイーブの危険性
http://www.codinghorror.com/blog/archives/001015.html

于 2009-11-06T04:22:22.527 に答える
2

Knuth シャッフル自体は、偏りがないことが証明されています。考えられる各シャッフルを生成する一連の操作が 1 つだけ存在します。ただし、PRNG が可能なすべてのシャッフルを表現するのに十分な状態のビットを持っている可能性は低いため、実際の問題は、PRNG が実際に生成するシャッフルのセットに関して「十分にランダム」であるかどうか、およびシード戦略が十分に安全かどうかです。 .

十分にランダムではないシャッフルの結果に依存するため、これを決定できるのはあなただけです。たとえば、実際のお金を扱っている場合は、暗号的に安全な PRNG に切り替えて、シード戦略を改善することをお勧めします。ほとんどのビルトイン PRNG は適切なランダム性を生成しますが、リバース エンジニアリングも非常に簡単であり、引数なしで seed() を呼び出すと、現在の時刻に基づいてシードされる可能性が高く、予測は非常に簡単です。

于 2009-11-06T09:37:19.353 に答える
0 
#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].
*/
}
于 2015-01-02T16:59:27.707 に答える