Ich habe ein int[] -Array der Länge N , das die Werte 0, 1, 2, ... (N-1) enthält, d. h. es repräsentiert eine Permutation ganzzahliger Indizes.
Was ist der effizienteste Weg, um festzustellen, ob die Permutation eine ungerade oder gerade Parität aufweist?
(Ich bin besonders daran interessiert zu vermeiden, Objekte für temporären Arbeitsraum zuzuweisen, wenn möglich ....)
Ich denke, Sie können dies in O (n) Zeit und O (n) Raum tun, indem Sie einfach den Zyklus berechnen Zerlegung .
Sie können die Zykluszerlegung in O (n) berechnen, indem Sie einfach mit dem ersten Element beginnen und dem Pfad folgen, bis Sie zum Anfang zurückkehren. Dies gibt Ihnen den ersten Zyklus. Markieren Sie jeden Knoten als besucht, während Sie dem Pfad folgen.
Wiederholen Sie dies für den nächsten nicht besuchten Knoten, bis alle Knoten als besucht markiert sind.
Die Parität eines Zyklus der Länge k ist (k-1)% 2, also können Sie einfach die Paritäten aller Zyklen addieren, die Sie entdeckt haben, um die Parität der Gesamtpermutation zu finden.
Eine Möglichkeit, die Knoten als besucht zu markieren, wäre, jedem Wert im Array bei dessen Besuch N hinzuzufügen. Sie wären dann in der Lage, einen abschließenden O (n) Durchlauf durchzuführen, um alle Zahlen wieder auf die ursprünglichen Werte zurückzustellen.
Betrachten Sie diesen Ansatz ...
Erhalten Sie aus der Permutation die umgekehrte Permutation, indem Sie die Zeilen und vertauschen Sortieren nach der Reihenfolge der obersten Zeile. Das ist O (nlogn)
Simulieren Sie dann die umgekehrte Permutation und zählen Sie die Swaps für O (n). Dies sollte die Parität der Permutation ergeben, gemäß diesem
Eine gerade Permutation kann als die Zusammensetzung eines geraden erhalten werden Zahl und nur eine gerade Anzahl von Austauschen (genannt Transpositionen) von zwei Elemente, während eine ungerade Permutation durch (nur) eine ungerade erhalten wird Anzahl der Transpositionen.
aus Wikipedia.
Hier ist ein Code, den ich herumliegen hatte, der eine umgekehrte Permutation durchführt. Ich habe ihn nur ein wenig geändert, um Swaps zu zählen. Sie können alle Erwähnungen von a entfernen, p enthält die umgekehrte Permutation.
Sie wollen die Parität der Anzahl der Inversionen. Sie können dies in O (n * log n) -Zeit mithilfe von merge sort tun, aber entweder verlieren Sie das ursprüngliche Array oder Sie benötigen zusätzlichen Speicher in der Reihenfolge O (n).
Ein einfacher Algorithmus, der O (n) Extra-Raum verwendet und O (n * log n) ist:
%Vor%Das heißt, ich denke nicht, dass es im sublinearen Speicher möglich ist. Siehe auch:
Ich wählte die Antwort von Peter de Rivaz als die richtige Antwort aus, da dies der algorithmische Ansatz war, den ich am Ende benutzte.
Allerdings habe ich ein paar zusätzliche Optimierungen verwendet, also dachte ich, ich würde sie teilen:
java.util.BitSet , um die besuchten Elemente zu speichern Code unten:
%Vor%Tags und Links algorithm java permutation