Anzahl der Fixpunkte

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

${\displaystyle 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

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

und

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

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

Anzahl der Anstiege

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

${\displaystyle 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

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

und

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

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

Anzahl der Fehlstände

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

${\displaystyle 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

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

und

${\displaystyle \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 ${\displaystyle n\to \infty }$ asymptotisch normalverteilt.

Anzahl der Zyklen

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

${\displaystyle 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

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

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

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

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

Direktes Verfahren

Bei einem direkten Ansatz wird zunächst eine aus den Zahlen von ${\displaystyle 1}$ bis ${\displaystyle n}$ bestehende Liste betrachtet. Nach einer Ziehung einer uniform verteilten Zufallszahl zwischen ${\displaystyle 1}$ und ${\displaystyle 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 ${\displaystyle 1}$ und ${\displaystyle 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

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 ${\displaystyle O(n)}$ Operationen, sodass das Gesamtverfahren eine Laufzeitkomplexität der Ordnung

${\displaystyle 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

Eine Verbesserung ist das Fisher-Yates-Verfahren (nach Ronald Fisher und Frank Yates). Dieses Verfahren arbeitet am Platz, das heißt, die Zahlen werden im Feld umsortiert und nicht in zusätzlichen Speicher kopiert. Sie werden schrittweise umsortiert, so 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. Das Verfahren in Pseudocode:

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

Die Initialisierung kann dabei, wie im Codebeispiel, mit der identischen Permutation erfolgen, man kann aber auch von einer beliebigen Permutation ausgehen, die dann zufällig umsortiert wird. Die Permutationsroutine kann somit iterativ aufgerufen werden, wobei sie jeweils die vorherige Zufallspermutation umsortiert. 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 ${\displaystyle O(n)}$, eine erhebliche Verbesserung gegenüber dem direkten Verfahren. In der nebenstehenden Tabelle wird das Verfahren anhand eines Beispiels illustriert, bei dem eine pseudozufällige Permutation der Länge sechs erzeugt wird. Die jeweils miteinander vertauschten Zahlen sind dabei unterstrichen. Es kann vorkommen, dass eine Zahl mit sich selbst vertauscht wird, was keinen Effekt hat. Es wurden die gleichen Zufallszahlen verwendet wie in dem Beispiel zum direkten Verfahren, allerdings ist die Ergebnispermutation hier eine andere.

Dieses Verfahren ist beispielsweise in dem numerischen Softwarepaket MATLAB als eingebaute Funktion randperm verfügbar.