Zufällige Permutation

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Playing card spade 7 - vertical cut.pngPlaying card spade 3 - vertical cut.pngPlaying card spade J - vertical cut.pngPlaying card spade 5 - vertical cut.pngPlaying card spade 9 - vertical cut.pngPlaying card spade A - vertical cut.pngPlaying card spade Q - vertical cut.pngPlaying card spade 2 - vertical cut.pngPlaying card spade 6 - vertical cut.pngPlaying card spade 10 - vertical cut.pngPlaying card spade K - vertical cut.pngPlaying card spade 8 - vertical cut.pngPlaying card spade 4.svg
Eine Realisierung einer zufälligen Permutation der Spielkarten einer Farbe

Eine zufällige Permutation oder Zufallspermutation ist in der Mathematik eine zufällige Anordnung einer 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 gleichverteilte Zufallsvariablen aus einem diskreten Wahrscheinlichkeitsraum angesehen, deren Werte Permutationen sind. So können auch Kennzahlen zufälliger Permutationen, wie die Anzahl der Fixpunkte, Fehlstände oder Zyklen, als diskrete Zufallsvariablen angesehen werden, deren Wahrscheinlichkeitsverteilungen dann analysiert werden. Im Computer können pseudozufä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[Bearbeiten]

Ist S_n die symmetrische Gruppe aller Permutationen der Menge \{ 1, \ldots , n \}, dann ist eine zufällige Permutation eine auf S_n gleichverteilte Zufallsvariable \Pi, das heißt eine Abbildung \Pi\colon \Omega \to S_n von einem Wahrscheinlichkeitsraum (\Omega, \mathcal A, P), sodass

P(\Pi = \pi) = \frac{1}{n!}

für alle Permutationen \pi \in S_n gilt. Allgemeiner können auch Permutationen beliebiger endlicher Mengen, beispielsweise Alphabete, betrachtet werden. Zur Analyse der mathematischen Eigenschaften ist jedoch eine Beschränkung auf die ersten n natürlichen Zahlen möglich.

Beispiel[Bearbeiten]

Die Menge S_3 besteht aus den sechs Permutationen der Zahlen 1, 2 und 3, in Tupeldarstellung

S_3 = \{ (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1) \}.

Eine zufällige Permutation \Pi realisiert jede dieser sechs Permutationen \pi \in S_3 mit der gleichen Wahrscheinlichkeit

P(\Pi = \pi) = \frac{1}{6}.

Wird als zugrunde liegender Wahrscheinlichkeitsraum (S_3, \mathcal{P}(S_3), P) mit P(\{\pi\}) = \tfrac{1}{6} für alle \pi \in S_3 gewählt, so kann \Pi durch die identische Abbildung dargestellt werden.

Eigenschaften[Bearbeiten]

Zufälligen Permutationen zugeordnete Größen, wie die Anzahl der Fehlstände oder Zyklen, können ebenfalls als diskrete Zufallsvariablen X = X(\Pi) 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 \N_0 annimmt, dann wird die zugehörige wahrscheinlichkeitserzeugende Funktion durch

g(x) = \sum_{k=0}^\infty P_X(k) \cdot x^k

definiert. Dabei handelt es sich hier 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 Wahrscheinlichkeitsverteilungen, Erwartungswerte und Varianzen einiger wichtiger Kenngrößen zufälliger Permutationen angegeben.

Anzahl der Fixpunkte[Bearbeiten]

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 die Form

g(x) = \sum_{k=0}^n \frac{D_{n,k}}{n!} \, x^k = \sum_{k=0}^n \sum_{j=0}^{n-k} \frac{(-1)^j \, x^k}{j! \, 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.[1]

Anzahl der Anstiege[Bearbeiten]

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

Ein Anstieg in einer Permutation \pi ist eine Zahl i, für die \pi(i+1) > \pi(i) gilt. Die Anzahl der Permutationen \pi \in S_n mit genau k Anstiegen (analog Abstiegen) wird durch die Euler-Zahlen A_{n,k} angegeben (Folge A008292 in OEIS). Die wahrscheinlichkeitserzeugende Funktion der Anzahl der Anstiege einer Permutation \pi \in S_n hat die Form

g(x) = \sum_{k=0}^{n-1} \frac{A_{n,k}}{n!} \, x^k = \frac{1}{n!} \sum_{k=0}^{n-1} \sum_{j=0}^k\,(-1)^j \binom{n+1}{j} (k+1-j)^n \, x^k.

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

\operatorname{E}(X) = \frac{n-1}{2}

und

\operatorname{Var}(X) = \frac{n+1}{12}.

Die Anzahl der Anstiege in einer zufälligen Permutation ist bei entsprechender Normierung für n \to \infty asymptotisch normalverteilt.[2]

Anzahl der Fehlstände[Bearbeiten]

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 die Form[3]

g(x) = \sum_{k=0}^{n(n-1)/2} \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 gilt damit

\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.[4]

Anzahl der Zyklen[Bearbeiten]

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 vollständig in 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 die Form

g(x) = \sum_{k=1}^n \frac{s_{n,k}}{n!} \, x^k = \frac{1}{n!} \prod_{k=1}^{n} (x+k-1).

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

\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.[5]

Erzeugung[Bearbeiten]

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 pseudozufällige Permutation entsteht.

Direktes Verfahren[Bearbeiten]

Bei einem direkten Ansatz wird zunächst eine aus den Zahlen von 1 bis n bestehende Liste betrachtet. Nach einer Ziehung einer uniform verteilten Zufallszahl zwischen 1 und n (einschließlich) wird das entsprechende Listenelement als die erste Zahl der Ergebnispermutation notiert und dieses Element anschließend aus der Liste gestrichen. Im nächsten Schritt wird dann eine uniform verteilte Zufallszahl zwischen 1 und n-1 gezogen, das entsprechende Listenelement als zweite Zahl der Ergebnispermutation notiert und dieses Element ebenfalls wieder gestrichen. Dieses Vorgehen wird fortgesetzt, bis schließlich keine Zahl mehr in der Liste vorhanden 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]                           // Feld 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 Verfahren 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 einer Liste 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 pseudozufälligen Permutation der Länge sechs. Die in jedem Schritt ausgewählte und damit eliminierte Zahl ist dabei durchgestrichen dargestellt.

Fisher-Yates-Verfahren[Bearbeiten]

Eine Verbesserung stellt das Fisher-Yates-Verfahren (nach Ronald Fisher und Frank Yates) dar. Dieses Verfahren arbeitet zudem am Platz, das heißt bei einem gegebenen vorinitialisierten 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 die ausgewählte Zahl ans Ende des aktuell betrachteten Teilfelds 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 wird. Da die Vertauschung zweier Elemente eines Felds fester Größe 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 pseudozufällige Permutation der Länge sechs erzeugt wird. Die jeweils miteinander vertauschten Zahlen sind dabei unterstrichen dargestellt. Der letzte Schritt kann auch weggelassen werden, da hier nie eine Vertauschung stattfindet. Es wurden die gleichen Zufallszahlen verwendet, wie in dem Beispiel zum direkten Verfahren, allerdings ist die Ergebnispermutation hier eine andere.

Dieses Verfahren wird beispielsweise in dem numerischen Softwarepaket MATLAB als eingebaute Funktion randperm zur Verfügung gestellt.[6]

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1.  Alan Camina, Barry Lewis: An Introduction to Enumeration. Springer, 2011, ISBN 0-857-29600-0, S. 140.
  2.  Philippe Flajolet, Robert Sedgewick: Analytic Combinatorics. Cambridge University Press, 2009, S. 658.
  3.  Donald E. Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching. S. 15–16.
  4.  Vladimir Nikolaevič Sačkov: Probabilistic Methods in Combinatorial Analysis. Cambridge University Press, 1997, S. 30.
  5.  Hosam M. Mahmoud: Sorting: A Distribution Theory. John Wiley & Sons, 2000, ISBN 0471327107, S. 48.
  6. randperm. In: MATLAB Documentation Center. The MathWorks, abgerufen am 7. Dezember 2013.