Überprüfen Sie, ob der Knuth Shuffle -Algorithmus so unvoreingenommen wie möglich ist

Question

Ich implementiere a Knuth Shuffle Für ein C ++ - Projekt arbeite ich. Ich versuche, die unvoreingenommensten Ergebnisse aus meinem Shuffle zu erzielen (und ich bin kein Experte für (Pseudo) zufällige Zahlengenerierung). Ich möchte nur sicherstellen, dass dies die unvoreingenommenste Shuffle -Implementierung ist.

draw_t ist ein Byte -Typ (typedef'D zu unsigned char). items ist die Anzahl der Elemente in der Liste. Ich habe den Code für angegeben random::get( draw_t max ) unter.

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

Die zufällige Funktion, die ich verwende, wurde geändert, um zu eliminieren Modulo -Voreingenommenheit. RAND_MAX wird zugewiesen 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 );
}

Answer 1

Nun, eine Sache, die Sie als Black-Box-Test machen konnten, ist eine relativ kleine Arraygröße, eine große Anzahl von Mischungen darauf auszuführen, zu zählen, wie oft Sie jede Permutation beobachten und dann durchführen Pearsons Chi-Quadrat Test, um festzustellen, ob die Ergebnisse gleichmäßig über den Permutationsraum verteilt sind.

Andererseits hat sich der Knuth Shuffle, auch bekannt als Fisher-Yates-Shuffle, als unvoreingenommen erwiesen, solange der zufällige Zahlengenerator, aus dem die Indizes stammen, unvoreingenommen ist.

Answer 2

Wenn ich das richtig sehe, deine random::get (max) schließt nicht ein max.

Diese Linie:

draw_t push_index = random::get( pull_index );

erzeugt dann einen "klassischen" außerhalb des Fehlers als Ihr "klassisch" pull_index und push_index Falsch kann niemals gleich sein. Dies erzeugt eine subtile Tendenz, die Sie nie vor dem Shuffle einen Gegenstand haben können. In einem extremen Beispiel würden zwei Elementlisten unter diesem "Shuffle" immer umgekehrt.

Answer 3

Schauen Sie sich diesen Artikel von Jeff Atwood an:

Mischen
http://www.codinghorror.com/blog/archives/001008.html

Siehe auch:

Die Gefahr von Naivität
http://www.codinghorror.com/blog/archives/001015.html

Answer 4

Der Knuth Shuffle selbst ist nachweislich unvoreingenommen: Es gibt genau eine Reihe von Operationen, die jedes mögliche Shuffle liefern. Es ist unwahrscheinlich, dass Ihr PRNG über genügend Zustandsstücke verfügt, um jedes mögliche Shuffle auszudrücken. Die eigentliche Frage ist also, ob Ihre PRNG in Bezug auf die tatsächlich erzeugenden Shuffles „zufällig genug“ ist und ob Ihre Stategie sicher genug ist .

Nur Sie können dies entscheiden, da es von den Folgen eines Shuffle abhängt, der nicht zufällig genug ist. Wenn Sie beispielsweise mit echtem Geld zu tun haben, würde ich empfehlen, zu einem kryptografisch sicheren PRNG zu wechseln und Ihre Seeding -Strategie zu verbessern. Obwohl die meisten integrierten PRNGs eine gute Zufälligkeit erzeugen, sind sie auch ziemlich einfach zu kontinuierlich, und das Aufrufen von Seed () ohne Argumente ist wahrscheinlich eine Aussaat auf der Grundlage der aktuellen Zeit, was ziemlich leicht vorherzusagen ist.

Answer 5

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