Betrachten Sie eine Permutation der ganzen Zahlen 1
, ... n
, wie diese für n = 6
:
[5,2,4,3,6,1]
Wenn Sie die Permutation als Zuordnung von [1,2,3,4,5,6]
zu betrachten [5,2,4,3,6,1]
, kann die Permutation in disjunkte Zyklen zerlegt werden . Ein Zyklus ist eine Teilmenge von Elementen, die einander zugeordnet sind. Beispielsweise 1
wird zugeordnet 5
, das zugeordnet wird 6
, das zurück zugeordnet wird 1
. Ein Zyklus ist also [1,5,6]
. Die anderen Zyklen sind [2]
und [3,4]
. Somit ist die Anzahl der Zyklen für diese Permutation 3
.
Im Allgemeinen sind die Zyklen einer Permutation eindeutig (bis zur Reihenfolge), und die Anzahl der Zyklen für eine Permutation der Größe n
variiert von 1
bis n
.
Die Herausforderung
Bei einer nicht leeren Permutation wird die Anzahl der Zyklen ausgegeben.
Eingang ist ein Array , gebildet durch die n
ganzen Zahlen 1
, 2
, ..., n
gegeben n > 0
. Jede Ganzzahl kommt genau einmal vor. Die Reihenfolge, in der sie angezeigt werden, definiert die Permutation wie im obigen Beispiel.
Anstelle eines Arrays können Sie eine Liste, eine Zeichenfolge mit einem Trennzeichen zwischen den Zahlen, eine separate Eingabe für jede Zahl oder alles verwenden, was sinnvoll ist.
Für eine Permutation der Größe n
können Sie anstelle der 1-basierten Menge von Ganzzahlen 1
... n
die 0-basierte Menge 0
, ..., konsistent verwenden n-1
. Wenn ja, geben Sie dies bitte in Ihrer Antwort an.
Der Code sollte für Arbeit n
an bis 20
in einer angemessenen Zeit, sagen wir weniger als eine Minute.
Code Golf. Alle eingebauten erlaubt.
Testfälle
Dies setzt eine 1-basierte Array-Eingabe voraus.
[1] -> 1
[3,2,1] -> 2
[2,3,4,5,1] -> 1
[5,2,4,3,6,1] -> 3
[8,6,4,5,2,1,7,3] -> 2
[4,5,11,12,7,1,3,9,10,6,8,2] -> 1
[4,2,5,11,12,7,1,3,9,10,6,8] -> 5
[5,8,6,18,16,9,14,10,11,12,4,20,15,19,2,17,1,13,7,3] -> 3
[14,5,17,15,10,18,1,3,4,13,11,16,2,12,9,7,20,6,19,8] -> 7
verbunden
Diese verwandte Herausforderung fragt nach den tatsächlichen Zyklen der Permutation, nicht nach deren Anzahl. Das Erfordernis nur der Anzahl von Zyklen kann zu kürzeren Algorithmen führen, die die Erzeugung der tatsächlichen Zyklen umgehen.
quelle
1
, ...,n
in dieser Reihenfolge. Können Sie klarstellen, wie eine Zuordnung eine Eingabe sein kann? Ist es eine Datenstruktur?dict
. Ich möchte{1: 2, 2: 1}
als Eingabe statt haben[2, 1]
.Antworten:
J, 4 Bytes
Dies setzt voraus, dass die Permutation auf 0 basiert. Es verwendet das eingebaute Element,
C.
das eine Liste von Zyklen ausgibt, die eine direkte Permutation darstellt. Dann#
bestehen@
auf , dass die Anzahl der Zyklen in dieser Liste zurückgibt.Probieren Sie es hier aus.
quelle
JavaScript,
9998 BytesBei dieser Lösung wird davon ausgegangen, dass das Array und seine Werte nullindiziert sind (z
[2, 1, 0]
. B. ).Erläuterung
quelle
Mathematica, 45 Bytes
Es generiert ein Diagramm und zählt die verbundenen Komponenten.
quelle
Mathematica,
372827 BytesDanke @alephalpha für das Speichern von 9 Bytes und @miles für 1 weiteres Byte.
quelle
PermutationCycles[#,Length]&
PermutationCycles
ein zweites Argument verwenden könnte, um den Kopf seiner Ausgabe zu verändern. Sie können auch die Infixnotation verwenden, um ein weiteres Byte zu speichern#~PermutationCycles~Length&
.#&
ist ein gutes Stück kürzer alsIdentity
. ;)Python,
776967 Bytesquelle
(not p[i-1])
kann gemacht werden als0**p[i-1]
Jelly,
12109 Bytes1 Byte dank @ Dennis gespeichert .
Dies verwendet 1-basierte Permutationen. Es funktioniert, indem die Permutation wiederholt angewendet wird, bis eine vorherige Permutation erreicht ist, während die vorherigen Werte beibehalten werden. Durch Verfolgen der Änderungen wird die Umlaufbahn für jeden Wert in den Spalten dieser Tabelle erstellt. Durch Ermitteln des Minimums oder Maximums jeder Spalte kann dann eine Bezeichnung für diesen Zyklus erstellt werden. Deduplizieren Sie dann die Liste der Bezeichnungen und ermitteln Sie die Länge, die der Anzahl der getrennten Zyklen entspricht.
Probieren Sie es hier aus.
Erläuterung
quelle
ị³$ÐĿ«/QL
sollte arbeiten.Python, 64 Bytes
Dieser Code ist idiomatisch und lesbar. Verwendet die 0-Indizierung.
Bei jedem Wert wird geprüft, auf was und auf was der angegebene Wert und auf den kleineren der beiden Werte verweist. Nach genügend Wiederholungen zeigt jedes Element auf das kleinste Element seines Zyklus. Die Anzahl der verschiedenen Elemente, auf die gezeigt wird, ist dann die Anzahl der Zyklen.
Es genügt,
n
Iterationen durchzuführen. Alternativ können wir iterieren, bis sich die Liste nicht mehr ändert. Diese Strategie gab mir eine rekursive Funktion der gleichen Länge, 64 Bytes:Die Reduzierung betrug 65 Bytes
Die
set(_)
Konvertierungen können{*_}
in Python 3.5 verkürzt werden , wodurch 2 Byte eingespart werden.quelle
Haskell, 111 Bytes
Verwendet eine 0-basierte Indizierung
quelle
1l!i|iIi!!1ll1|
Pyth, 9 Bytes
Verwendet 0-basierte Indizes. Probieren Sie es online aus .
Wie es funktioniert
quelle
JavaScript (ES6), 49 Byte
Verwendet nullbasierte Indizierung. Erläuterung:
reduce
Wird verwendet, um die innere Funktiong
für jedes Element des Arrays aufzurufen .c
ist die Anzahl der Zyklen,e
ist das Array-Element,i
ist der Array-Index. Wenn das Element kleiner als der Index ist, handelt es sich um einen potenziellen Zyklus. Das Element wird zum rekursiven Indizieren in das Array verwendet, um das nächste Element im Zyklus zu finden. Wenn wir mit dem ursprünglichen Index begonnen haben oder am Ende stehen, ist dies ein neuer Zyklus und wir erhöhen die Zykluszahl. Wenn wir irgendwann einen Wert finden, der größer als der Index ist, werden wir diesen Zyklus später zählen.quelle
[2,1,0,3,4,5]
, stürzte er mit der Meldung "Maximale Aufrufstapelgröße überschritten" ab.C 90 Bytes
Aufruf
f()
mit einem veränderlichenint
Array, 1-basierte Indizierung. Der zweite Parameter ist die Größe des Arrays. Die Funktion gibt die Anzahl der Zyklen zurück.Probiere es auf ideone aus .
Der Algorithmus:
quelle
GAP , 30 Bytes
Das zweite Argument
Cycles
gibt die Menge an, auf die die Permutation angewendet werden soll:quelle