Zufällige Permutation

Eine zufällige Permutation oder Zufallspermutation ist in der Mathematik eine zufällige Anordnung einer endlichen Menge von Objekten. Beispielsweise ist das Mischen der Karten eines Kartenspiels (im Idealfall) eine zufällige Permutation der Karten. In der Stochastik werden zufällige Permutationen als Elementarereignisse in einem diskreten Wahrscheinlichkeitsraum angesehen. So können Kennzahlen, wie die Anzahl der Fixpunkte, Fehlstände oder Zyklen, als diskrete Zufallsvariablen angesehen werden, deren Wahrscheinlichkeitsverteilungen dann untersucht werden. Im Computer können zufällige Permutationen effizient mit dem Fisher-Yates-Verfahren generiert werden. Zufällige Permutationen werden unter anderem bei der Analyse von Sortierverfahren, in der Kryptographie und Kodierungstheorie sowie im Rahmen randomisierter Algorithmen untersucht.

Definition

Gegeben sei die Menge $S_{n}$ der Permutationen der Zahlen von $1$ bis $n$, also

$S_{n}=\{\pi \colon \{1,\ldots ,n\}\to \{1,\ldots ,n\}\mid \pi ~{\text{ist bijektiv}}\}$.

Man betrachtet nun den diskreten Wahrscheinlichkeitsraum $(S_{n},{\mathcal {P}}(S_{n}),P)$ mit der Potenzmenge ${\mathcal {P}}$ und dem durch

$P(\{\pi \})={\frac {1}{n!}}$   für alle $\pi \in S_{n}$

definierten Wahrscheinlichkeitsmaß $P$. Dieser Wahrscheinlichkeitsraum ist ein Laplace-Raum, in dem jede Permutation die gleiche Wahrscheinlichkeit besitzt, und seine Elementarereignisse heißen zufällige Permutationen. Allgemeiner können auch Permutationen beliebiger endlicher Mengen, beispielsweise Alphabete, betrachtet werden, zur Analyse der mathematischen Eigenschaften kann man sich jedoch auf die ersten $n$ natürlichen Zahlen beschränken.

Eigenschaften

Erzeugende Funktionen

Zufälligen Permutationen zugeordnete Größen, wie die Anzahl der Fixpunkte, Fehlstände oder Zyklen, können als diskrete Zufallsvariablen interpretiert werden. Die Wahrscheinlichkeitsverteilung dieser Zufallsvariablen ist allerdings im Allgemeinen nicht mehr gleichverteilt. Ein wichtiges Hilfsmittel bei der Analyse dieser Wahrscheinlichkeitsverteilungen sind erzeugende Funktionen. Ist $P_{X}(k)=P(X=k)$ die Wahrscheinlichkeitsfunktion, dass die Zufallsvariable $X$ den Wert $k\in \mathbb {N} _{0}$ annimmt, dann wird die zugehörige wahrscheinlichkeitserzeugende Funktion durch

$g(x)=\sum _{k=0}^{\infty }P_{X}(k)\cdot x^{k}$

für $0\leq x\leq 1$ definiert. Dabei handelt es sich um eine exponentiell erzeugende Funktion. Der Erwartungswert der Zufallsvariable $X$ ist dann durch

$\operatorname {E} (X)=\sum _{k=0}^{\infty }k\cdot P_{X}(k)=g'(1)$

gegeben und ihre Varianz entsprechend durch

$\operatorname {Var} (X)=\sum _{k=0}^{\infty }(k-\operatorname {E} (X))^{2}\cdot P_{X}(k)=g''(1)+g'(1)(1-g'(1))$.

Im Folgenden werden einige wichtige Wahrscheinlichkeitsverteilungen, ihre Erwartungswerte und ihre Varianzen angegeben.

Anzahl der Fixpunkte

Häufigkeitsverteilung der Anzahl der Fixpunkte in einer zufälligen Permutation der Länge 7

Ein Fixpunkt in einer Permutation $\pi$ ist eine Zahl $i\in \{1,\ldots ,n\}$, für die $\pi (i)=i$ gilt. Die Anzahl der Permutationen $\pi \in S_{n}$ mit genau $k$ Fixpunkten wird durch die Rencontres-Zahlen $D_{n,k}$ angegeben (Folge A008290 in OEIS). Die wahrscheinlichkeitserzeugende Funktion der Anzahl der Fixpunkte einer Permutation $\pi \in S_{n}$ hat somit die Form

$g(x)=\sum _{k=0}^{n}{\frac {D_{n,k}}{n!}}\,x^{k}=\sum _{k=0}^{n}{\frac {1}{k!}}\,\sum _{j=0}^{n-k}{\left(-1\right)^{j} \over j!}\,x^{k}$.

Für den Erwartungswert und die Varianz der Anzahl der Fixpunkte gilt damit

$\operatorname {E} (X)=\sum _{k=0}^{n-1}{\frac {D_{n-1,k}}{n!}}=1$

und

$\operatorname {Var} (X)=\sum _{k=0}^{n-2}{\frac {D_{n-2,k}}{n!}}=1$

Die Anzahl der Fixpunkte in einer zufälligen Permutation ist für $n\to \infty$ asymptotisch poisson-verteilt mit Intensität $\lambda =1$.

Anzahl der Fehlstände

Häufigkeitsverteilung der Anzahl der Fehlstände in einer zufälligen Permutation der Länge 7

Ein Fehlstand in einer Permutation $\pi$ ist ein Paar $(i,j)$, für das $i<j$ und $\pi (i)>\pi (j)$ gilt. Die Anzahl der Permutationen $\pi \in S_{n}$ mit genau $k$ Fehlständen wird durch die McMahon-Zahlen $M_{n,k}$ angegeben (Folge A008302 in OEIS). Die Wahrscheinlichkeitsfunktion der Anzahl der Fixpunkte einer Permutation $\pi \in S_{n}$ hat somit die Form

$g(x)=\sum _{k=0}^{n}{\frac {M_{n,k}}{n!}}\,x^{k}={\frac {1}{n!}}\prod _{i=1}^{n}\sum _{j=0}^{n-i}x^{j}={\frac {1}{n!}}\prod _{i=1}^{n}{\frac {1-x^{i}}{1-x}}$.

Für den Erwartungswert und die Varianz der Anzahl der Fehlstände erhält man

$\operatorname {E} (X)=\sum _{i=1}^{n}{\frac {i-1}{2}}={\frac {n(n-1)}{4}}$

und

$\operatorname {Var} (X)=\sum _{i=1}^{n}{\frac {i^{2}-1}{12}}={\frac {n(2n+5)(n-1)}{72}}$

Die Anzahl der Fehlstände in einer zufälligen Permutation ist bei entsprechender Normierung für $n\to \infty$ asymptotisch normalverteilt.

Anzahl der Zyklen

Häufigkeitsverteilung der Anzahl der Zyklen in einer zufälligen Permutation der Länge 7

Ein Zyklus in einer Permutation $\pi$ ist eine Folge verschiedener Zahlen $i_{1},i_{2},\ldots ,i_{k}$, für die $\pi (i_{j})=i_{j+1}$ für $j=1,\ldots ,k-1$ und $\pi (i_{k})=i_{1}$ gilt. Jede Permutation kann so in ein oder mehrere Zyklen zerlegt werden. Die Anzahl der Permutationen $\pi \in S_{n}$ mit genau $k$ Zyklen wird durch die Stirling-Zahlen der ersten Art $s_{n,k}$ angegeben (Folge A130534 in OEIS). Die wahrscheinlichkeitserzeugende Funktion der Anzahl der Zyklen einer Permutation $\pi \in S_{n}$ hat somit die Form

$g(x)=\sum _{k=0}^{n}{\frac {s_{n,k}}{n!}}\,x^{k}={\frac {1}{n!}}\sum _{k=0}^{n}\sum _{0<i_{1}<\ldots <i_{n-k}<n}\!\!\!i_{1}i_{2}\cdots i_{n-k}\,x^{k}$.

Für den Erwartungswert und die Varianz der Anzahl der Fehlstände erhält man

$\operatorname {E} (X)=\sum _{k=1}^{n}{\frac {1}{k}}=H_{n}$,

wobei $H_{n}$ die $n$-te harmonische Zahl ist, und

$\operatorname {Var} (X)=\sum _{k=1}^{n}{\frac {k-1}{k^{2}}}=H_{n}-H_{n}^{(2)}$,

wobei $H_{n}^{(2)}$ die $n$-te harmonische Zahl zweiter Ordnung ist. Die Anzahl der Zyklen in einer zufälligen Permutation ist bei entsprechender Normierung für $n\to \infty$ asymptotisch normalverteilt mit Erwartungswert und Varianz $\log n$.

Erzeugung

Eine wichtige Aufgabe bei der Untersuchung von Algorithmen, beispielsweise Sortierverfahren, im Rahmen von Monte-Carlo-Simulationen ist die Erzeugung zufälliger Permutationen auf dem Computer. Die Grundidee ist hierbei die Verwendung uniform verteilter Pseudozufallszahlen mit Hilfe geeigneter Zufallszahlengeneratoren. Diese Pseudozufallszahlen werden dann auf geeignete Weise kombiniert, sodass eine zufällige Permutation entsteht.

Direktes Verfahren

Bei dem direkten Verfahren betrachtet man zunächst das Tupel bestehend aus den Zahlen von $1$ bis $n$. Nun zieht man eine uniform verteilte Zufallszahl zwischen $1$ und $n$ (einschließlich), notiert das entsprechende Tupelelement als die erste Zahl der Ergebnispermutation und streicht dieses Element anschließend aus dem Tupel. Im nächsten Schritt zieht man eine uniform verteilte Zufallszahl zwischen $1$ und $n-1$, notiert das entsprechende Tupelelement als zweite Zahl der Ergebnispermutation und streicht dieses Element ebenfalls. Dieses Vorgehen wird fortgesetzt, bis schließlich keine Zahl mehr in dem Tupel vorhanden ist und damit die Ergebnispermutation vollständig ist. In Pseudocode kann dieses Verfahren wie folgt implementiert werden:

function randperm(n)
    P = zeroes(n)                       // Ergebnispermutation mit Nullen initialisieren
    N = [1:n]                           // Tupel mit den Zahlen von 1 bis n
    for i = 1 to n                      // Schleife über die Einträge von P
        z = random(n-i+1)               // Gleichverteilte Zufallszahl zwischen 1 und n-i+1
        P(i) = N(z)                     // Wähle als nächsten Eintrag die z-te verbleibende Zahl
        N = setdiff(N,N(z))             // Entferne diese Zahl aus den verbleibenden Zahlen
    end
    return P

Bereich	Zufallszahl	Auswahl	Ergebnis
1-6	5	1 2 3 4 5 6	5
1-5	3	1 2 3 4 6	5 3
1-4	4	1 2 4 6	5 3 6
1-3	1	1 2 4	5 3 6 1
1-2	2	2 4	5 3 6 1 4
1-1	1	2	5 3 6 1 4 2

Bei diesem Ansatz werden die Plätze der Reihe nach durchgegangen, wobei jedem Platz eine zufällig aus den jeweils noch verfügbaren Zahlen ausgewählte Zahl zugewiesen wird. Alternativ kann auch der duale Ansatz verfolgt werden, bei dem die Zahlen der Reihe nach durchgegangen werden, wobei jeder Zahl ein zufällig ausgewählter noch freier Platz zugewiesen wird. In beiden Fällen leidet die Effizienz des Verfahrens darunter, dass es aufwändig ist, ein bestimmtes Element aus einem Tupel zu entfernen, beziehungsweise einen bestimmten freien Platz zu finden. In einer Standardimplementierung benötigen diese Teilaufgaben im Mittel $O(n)$ Operationen, sodass das Gesamtverfahren eine Laufzeitkomplexität der Ordnung

$O(n^{2})$

aufweist. In der nebenstehenden Tabelle findet sich ein Beispiel für die Funktionsweise dieses Verfahrens bei der Erzeugung einer zufälligen Permutation der Länge sechs. Die in jedem Schritt ausgewählte und damit eliminierte Zahl ist dabei durchgestrichen dargestellt.

Fisher-Yates-Verfahren

Eine Verbesserung stellt das Fisher-Yates-Verfahren (nach Ronald Fisher und Frank Yates) dar. Dieses Verfahren arbeitet zudem am Platz, das heißt gegeben ein vorinitialisiertes Feld mit den Zahlen von $1$ bis $n$ werden diese Zahlen schrittweise derart umsortiert, dass am Ende eine zufällige Permutation entsteht. Um die aufwändige Suche nach einer noch nicht verwendeten Zahl zu vermeiden wird in jedem Schritt eine ausgewählte Zahl ans Ende der aktuellen Teilliste gestellt, indem sie mit der letzten noch nicht ausgewählten Zahl vertauscht wird. In Pseudocode stellt sich dieses Verfahren wie folgt dar:

function randperm(n)
    P = [1:n]                           // Initialisierung mit der identischen Permutation
    for i = n downto 1                  // Schleife über die Einträge von P
        z = random(i)                   // Gleichverteilte Zufallszahl zwischen 1 und i
        swap(P(i),P(z))                 // Vertausche die Zahlen an den Stellen i und z
    end
    return P

Bereich	Zufallszahl	Permutation
1-6	5	1 2 3 4 5 6
1-5	3	1 2 3 4 6 5
1-4	4	1 2 6 4 3 5
1-3	1	1 2 6 4 3 5
1-2	2	6 2 1 4 3 5
1-1	1	6 2 1 4 3 5

Die Initialisierung kann dabei, wie im Codebeispiel, mit der identischen Permutation erfolgen, es kann hier aber auch eine beliebige Permutation verwendet werden, die dann entsprechend umsortiert wird. Dies macht das Verfahren speziell für Simulationsanwendungen attraktiv, bei denen die Permutationsroutine iterativ aufgerufen werden kann. Da die Vertauschung zweier Elemente eines Tupels mit einem konstanten Aufwand erfolgt, besitzt das Fisher-Yates-Verfahren eine Laufzeitkomplexität der Ordnung

$O(n)$,

was eine erhebliche Verbesserung gegenüber dem direkten Verfahren darstellt. In der nebenstehenden Tabelle wird das Verfahren ebenfalls anhand eines Beispiels illustriert, bei dem wieder eine zufällige Permutation der Länge sechs erzeugt wird. Die jeweils miteinander vertauschten Zahlen sind dabei unterstrichen dargestellt. Es wurden die gleichen Zufallszahlen verwendet, wie in dem Beispiel zum direkten Verfahren, allerdings ist die Ergebnispermutation hier eine andere.

Siehe auch

• RC4, ein Verfahren zur Stromverschlüsselung, das zufällige Permutationen verwendet
• Golomb-Dickman-Konstante, die mittlere relative Länge des längsten Zyklus in einer Permutation für $n\to \infty$

Literatur

• Philippe Flajolet, Robert Sedgewick: Analytic Combinatorics. Cambridge University Press, 2009, ISBN 1-139-47716-1. 
• Donald E. Knuth: The Art of Computer Programming, Volume 2: Seminumerical Algorithms. 3. Auflage. Addison-Wesley, 1997, ISBN 0-201-89684-2. 
• Donald E. Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching. 2. Auflage. Addison-Wesley, 1998, ISBN 0-201-89685-0. 

Weblinks

• Eric W. Weisstein: Random Permutation. In: MathWorld (englisch).