Anzahl der Zyklen einer Permutation

23

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 1wird 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 nvariiert von 1bis n.

Die Herausforderung

Bei einer nicht leeren Permutation wird die Anzahl der Zyklen ausgegeben.

Eingang ist ein Array , gebildet durch die nganzen Zahlen 1, 2, ..., ngegeben 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 nkönnen Sie anstelle der 1-basierten Menge von Ganzzahlen 1... ndie 0-basierte Menge 0, ..., konsistent verwenden n-1. Wenn ja, geben Sie dies bitte in Ihrer Antwort an.

Der Code sollte für Arbeit nan bis 20in 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.

Luis Mendo
quelle
Egal, meine Frage, es steht in der Frage, dass 0-basierte Eingaben erlaubt sind.
Orlp
@orlp Das war schnell! Ich habe Ihre Frage nicht einmal gesehen
Luis Mendo
Können wir eine Zuordnung von Indizes zu Werten als Eingabe nehmen?
Kupfer
1
@Copper Ich denke ja, wenn die Domain des Mappings die Menge ist 1, ..., nin dieser Reihenfolge. Können Sie klarstellen, wie eine Zuordnung eine Eingabe sein kann? Ist es eine Datenstruktur?
Luis Mendo
@ LuisMendo Ja, es ist eine Datenstruktur, wie ein Python dict. Ich möchte {1: 2, 2: 1}als Eingabe statt haben [2, 1].
Kupfer

Antworten:

12

J, 4 Bytes

#@C.

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.

Meilen
quelle
1
Das ist Betrug! :)
Orlp
1
Ich hätte builtins verbieten sollen :-D
Luis Mendo
2
Builtins sind Liebe. Builtins sind Leben. Ich bin damit einverstanden, dass es mehr Spaß macht, wenn Builtins gesperrt werden. Sie können die Regel jederzeit ändern, bevor zu viele antworten.
Meilen
@miles Nein, ich lasse es so wie es ist. Gut gemacht!
Luis Mendo
7

JavaScript, 99 98 Bytes

Bei dieser Lösung wird davon ausgegangen, dass das Array und seine Werte nullindiziert sind (z [2, 1, 0]. B. ).

f=a=>{h={},i=c=0;while(i<a.length){s=i;while(!h[i]){h[i]=1;i=a[i]}c++;i=s;while(h[++i]);}return c}

Erläuterung

// assumes the array is valid and zero-indexed
var findCycles = (array) => {
    var hash = {};  // remembers visited nodes
    var index = 0;  // current node
    var count = 0;  // number of cycles
    var start;      // starting node of cycle

    // loop until all nodes visited
    while(index < array.length) {
        start = index;  // cache starting node

        // loop until found previously visited node
        while(!hash[index]) {
            hash[index] = 1;    // mark node as visited
            index = array[index];   // get next node
        }
        count++;    // increment number of cycles

        index = start + 1;  // assume next node is right after

        // loop until found unvisited node
        while(hash[index]) {
            index++;    // get next node
        }
    }

    return count;   // return number of cycles
};
kamoroso94
quelle
3
Willkommen bei PPCG! Schöne erste Antwort! Dies ist auch eine der besten, wenn nicht sogar die beste Antwort, die ich in meiner Erfahrung gesehen habe! Mach weiter so!
GamrCorps
Wow vielen Dank! Eigentlich musste ich nachsehen, wie man die Lambdas in JavaScript macht. Ich bin noch nicht so vertraut mit dem ES6-Zeug.
Kamoroso94
6

Mathematica, 45 Bytes

Length@ConnectedComponents@Thread[Sort@#->#]&

Es generiert ein Diagramm und zählt die verbundenen Komponenten.

Alephalpha
quelle
6

Mathematica, 37 28 27 Bytes

#~PermutationCycles~Length&

Danke @alephalpha für das Speichern von 9 Bytes und @miles für 1 weiteres Byte.

martin
quelle
3
PermutationCycles[#,Length]&
Alephalpha
3
Oh, das ist ordentlich. Ich wusste nicht, dass ich PermutationCyclesein 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&.
Meilen
1
Auch in Bezug auf Ihre ursprüngliche Lösung #&ist ein gutes Stück kürzer als Identity. ;)
Martin Ender
6

Python, 77 69 67 Bytes

f=lambda p,i=1:i and0 **p[i-1]+f(p[:i-1]+[0]+p[i:],p[i-1]or max(p))
orlp
quelle
(not p[i-1])kann gemacht werden als0**p[i-1]
xnor
5

Jelly, 12 10 9 Bytes

ị³$ÐĿ«/QL

1 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

ị³$ÐĿ«/QL  Input: permutation p
  $        Chain (ị³) as a monad
 ³           The input p
ị            For each value x, get the value at index x in p
   ÐĿ      Invoke it on p initially, and repeat it on its next value until it returns
           to a previous value and keep track of the results
           This will create a table where each column is the orbit of each value
     «/    Get the minimum value along each column of that table
       Q   Deduplicate
        L  Get the length and return
Meilen
quelle
Sehr schöner Ansatz!
Luis Mendo
ị³$ÐĿ«/QLsollte arbeiten.
Dennis
@ Tennis Wow, das ist ein ordentlicher Trick! Da jeder Zyklus disjunkt ist, reicht es aus, entweder die Max./Min. Zu nehmen und als Etikett zu verwenden, um + Länge für das Ergebnis zu deduplizieren.
Meilen
5

Python, 64 Bytes

l=input()
for _ in l:l=[min(x,l[x])for x in l]
print len(set(l))

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, nIterationen 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:

f=lambda l,p=0:len(set(l*(l==p)))or f([min(x,l[x])for x in l],l)

Die Reduzierung betrug 65 Bytes

lambda l:len(set(reduce(lambda l,_:[min(x,l[x])for x in l],l,l)))

Die set(_)Konvertierungen können {*_}in Python 3.5 verkürzt werden , wodurch 2 Byte eingespart werden.

xnor
quelle
4

Haskell, 111 Bytes

l!i|l!!i<0=l|1<2=(take i l++[-1]++drop(i+1)l)!(l!!i)
f(x:y)|x>=0=0|1<2=1+f y
c l|l==[-1|x<-l]=0|1<2=1+c(l!f l)

Verwendet eine 0-basierte Indizierung

Programm Mann
quelle
4
Verdammt, du solltest besser eine gute Programmierschrift haben :)1l!i|iIi!!1ll1|
orlp
@orlp und es ist 111 Bytes! : O
grooveplex
4

Pyth, 9 Bytes

l{mS.u@QN

Verwendet 0-basierte Indizes. Probieren Sie es online aus .

Wie es funktioniert

  m         map for d in input:
    .u        cumulative fixed-point: starting at N=d, repeatedly replace N with
      @QN       input[N]
              until a duplicate is found, and return all intermediate results
   S          sort
 {          deduplicate
l           length
Anders Kaseorg
quelle
3

JavaScript (ES6), 49 Byte

a=>a.reduce(g=(c,e,i)=>e<i?g(c,a[e],i):c+=e==i,0)

Verwendet nullbasierte Indizierung. Erläuterung: reduceWird verwendet, um die innere Funktion gfür jedes Element des Arrays aufzurufen . cist die Anzahl der Zyklen, eist das Array-Element, iist 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.

Neil
quelle
Als ich Ihren Code auf dem Array ausführte [2,1,0,3,4,5], stürzte er mit der Meldung "Maximale Aufrufstapelgröße überschritten" ab.
kamoroso94
1
@ kamoroso94 Tut mir leid, ein Tippfehler hatte sich eingeschlichen. Sollte jetzt behoben sein.
Neil
2

C 90 Bytes

Aufruf f()mit einem veränderlichen intArray, 1-basierte Indizierung. Der zweite Parameter ist die Größe des Arrays. Die Funktion gibt die Anzahl der Zyklen zurück.

i,j,c;f(a,n)int*a;{for(c=i=0;i<n;++i)for(j=0,c+=!!a[i];a[i];a[i]=0,i=j-1)j=a[i];return c;}

Probiere es auf ideone aus .

Der Algorithmus:

For each index
    If index is non-zero
        Increment counter
        Traverse the cycle, replacing each index in it with 0.
owacoder
quelle
2

GAP , 30 Bytes

Das zweite Argument Cyclesgibt die Menge an, auf die die Permutation angewendet werden soll:

l->Size(Cycles(PermList(l),l))
Christian Sievers
quelle