Zufällige Permutation - Random permutation

Eine zufällige Permutation ist eine zufällige Reihenfolge von einem Satz von Objekten, das heißt, eine Permutation -wertigen Zufallsvariable . Die Verwendung von Zufallspermutationen ist oft grundlegend für Gebiete, die randomisierte Algorithmen verwenden, wie etwa Codierungstheorie , Kryptographie und Simulation . Ein gutes Beispiel für eine zufällige Permutation ist das Mischen eines Kartenspiels : Dies ist idealerweise eine zufällige Permutation der 52 Karten.

Generieren von zufälligen Permutationen

Brute-Force-Methode für den Eintritt nach dem anderen

Ein Verfahren zur Herstellung eine Zufallspermutation eines Satzes von Länge zu erzeugen n gleichmäßig zufällig (dh jede der n ! Permutationen mit gleicher Wahrscheinlichkeit auftritt) wird zur Erzeugung Sequenz durch eine Zufallszahl zwischen 1 und wobei n der Reihe nach , um sicherzustellen , dass es keine Wiederholung ist und diese Folge ( x ₁ , ..., x _n ) als Permutation interpretiert

${\displaystyle {\begin{pmatrix}1&2&3&\cdots &n\\x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\end{pmatrix}},}$

hier in zweizeiliger Notation dargestellt .

Diese Brute-Force-Methode erfordert gelegentliche Wiederholungsversuche, wenn die ausgewählte Zufallszahl eine Wiederholung einer bereits ausgewählten Zahl ist. Dies kann vermieden werden, wenn man im i- ten Schritt (wenn x ₁ , ..., x _{i − 1} bereits gewählt wurde) eine Zahl j zufällig zwischen 1 und n − i + 1 wählt und x _i gleich . setzt zur j- ten größten der nicht gewählten Zahlen.

Fisher-Yates mischt

Ein einfacher Algorithmus zum Generieren einer zufälligen Permutation von n Elementen ohne Wiederholungen, bekannt als Fisher-Yates-Shuffle , besteht darin, mit einer beliebigen Permutation (z. B. der Identitätspermutation ) zu beginnen und dann die Positionen 0 bis n − 2 . zu durchlaufen (wir verwenden eine Konvention, bei der das erste Element den Index 0 hat und das letzte Element den Index n − 1), und für jede Position i tausche ich das gerade dort befindliche Element gegen ein zufällig ausgewähltes Element aus den Positionen i bis n − 1 (das Ende) , inklusive. Es ist leicht zu überprüfen, dass jede Permutation von n Elementen von diesem Algorithmus mit einer Wahrscheinlichkeit von genau 1/ n ! erzeugt wird, was eine gleichmäßige Verteilung über alle diese Permutationen ergibt.

unsigned uniform(unsigned m); /* Returns a random integer 0 <= uniform(m) <= m-1 with uniform distribution */

void initialize_and_permute(unsigned permutation[], unsigned n)
{
    unsigned i;
    for (i = 0; i <= n-2; i++) {
        unsigned j = i+uniform(n-i); /* A random integer such that i ≤ j < n */
        swap(permutation[i], permutation[j]);   /* Swap the randomly picked element with permutation[i] */
    }
}

Beachten Sie, dass, wenn die uniform()Funktion einfach so implementiert wird, random() % (m)eine Verzerrung in die Ergebnisse eingeführt wird, wenn die Anzahl der Rückgabewerte von random()kein Vielfaches von m ist, dies jedoch unbedeutend wird, wenn die Anzahl der Rückgabewerte random()von Größenordnungen größer als m ist.

Statistiken zu zufälligen Permutationen

Fixpunkte

Die Wahrscheinlichkeitsverteilung der Anzahl von Fixpunkten in einer gleichverteilten Zufallspermutation nähert sich mit wachsendem n einer Poisson-Verteilung mit Erwartungswert 1 an . Insbesondere ist es eine elegante Anwendung des Einschluss-Ausschluss-Prinzips zu zeigen, dass die Wahrscheinlichkeit, dass es keine Fixpunkte gibt, gegen 1/ e geht . Wenn n groß genug ist, ist die Wahrscheinlichkeitsverteilung von Fixpunkten fast die Poisson-Verteilung mit Erwartungswert 1. Die ersten n Momente dieser Verteilung sind genau die der Poisson-Verteilung.

Zufallstests

Wie bei allen Zufallsprozessen hängt die Qualität der resultierenden Verteilung einer Implementierung eines randomisierten Algorithmus wie dem Knuth-Shuffle (dh wie nahe sie an der gewünschten Gleichverteilung liegt) von der Qualität der zugrunde liegenden Zufallsquelle ab, wie z ein Pseudozufallszahlengenerator . Es gibt viele mögliche Zufallstests für zufällige Permutationen, wie zum Beispiel einige der Diehard-Tests . Ein typisches Beispiel für einen solchen Test besteht darin, eine Permutationsstatistik zu nehmen , deren Verteilung bekannt ist, und zu testen, ob die Verteilung dieser Statistik auf einem Satz von zufällig erzeugten Permutationen der wahren Verteilung sehr nahe kommt.

Siehe auch

• Die Stichprobenformel von Ewens – eine Verbindung zur Populationsgenetik
• Faro-Shuffle
• Golomb-Dickman-Konstante
• Zufällige Permutationsstatistiken
• Mischalgorithmen – Zufallssortiermethode, iterative Austauschmethode

Verweise

Externe Links

• Zufällige Permutation bei MathWorld
• Zufällige Permutationsgenerierung -- detaillierte und praktische Erklärung des Knuth-Shuffle-Algorithmus und seiner Varianten zur Erzeugung von k -Permutationen (Permutationen von k Elementen ausgewählt aus einer Liste) und k -Untermengen (Erzeugung einer Untermenge der Elemente in der Liste ohne Ersetzung) mit Pseudocode