Wie erzeugt man zufällig eine Permutation P der ersten n natürlichen Zahlen, die P [i]! = I erfüllt?

Question

Ich möchte nach dem Zufallsprinzip eine Permutation P der ersten n natürlichen Zahlen erzeugen, und es muss die P[i] != i für jede i<n erfüllen.

Wie kann ich es effizient machen?

Die erste Methode, die ich gefunden habe, ist nur zufällig Zahlen für jede Position nach dem Zufallsprinzip zu wählen. Wie auch immer, ich glaube, es scheint nicht die Zufälligkeit zu garantieren.

Zum Beispiel im Fall von 4 Zahlen, wenn ich (zufällig) 2,3 für die ersten beiden Nummern wähle, dann könnte die Konfiguration für die letzten beiden Nummern entweder 0,1 oder 1,0 sein. Wenn ich für die ersten beiden die Option 1,2 wähle, dann ist die einzige verfügbare Option 3,0, da das letzte Bit nicht 3 sein kann. So scheint es die Wahrscheinlichkeit von 1,2,3,0 ist doppelt so hoch wie 2,3,0,1, oder?

Eine andere Sache zu tun ist zufällig eine Permutation zu generieren und ablehnen, wenn es die Bedingung nicht erfüllt, aber die Zeit Komplexität dafür kann nicht garantiert werden.

Answer 1

Sie könnten versuchen und Fehler mit Fisher-Yates shuffle. Die Wahrscheinlichkeit, eine Permutation P mit festen Punkten zu berechnen, ist 1-1/e, was bedeutet, dass die erwartete Anzahl von Versuchen e (oder ungefähr drei) ist.

Hier verwende ich die bekannte Tatsache, dass, wenn die Wahrscheinlichkeit, Köpfe zu sehen, wenn eine voreingenommene Münze wirft p dann die erwartete Anzahl von Versuchen, bis die ersten Köpfe ist 1/p.

Die gesamte erwartete Laufzeit ist dann O(n).

Beachten Sie auch, dass asymptotisch optimal ist, da jeder Algorithmus, der eine zufällige Permutation ohne Fixpunkte berechnet, alle Elemente berühren muss.

Pseudo-Code:

generateRandomPermutation(n) 
    do 
     generate a random permutation P of {1,2,3,...,n} with Fisher-Yates // O(n) 
    while there exists i with P[i] = i // Expected nr of iterations is e 
    return P