Konjugieren Sie Permutationen

17

Eine Permutation der Größe n ist eine Neuordnung der ersten n positiven ganzen Zahlen. (Das bedeutet, dass jede Ganzzahl genau einmal vorkommt.) Permutationen können wie Funktionen behandelt werden, die die Reihenfolge einer Liste von Elementen der Größe n ändern . Beispielsweise

(4 1 2 3) ["a", "b", "c", "d"] = ["d", "a", "b", "c"]

Somit können Permutationen wie Funktionen zusammengesetzt werden.

(4 1 2 3)(2 1 3 4) = (4 2 1 3)

Dies bringt viele interessante Eigenschaften mit sich. Heute konzentrieren wir uns auf die Konjugation . Die Permutationen y und x (beide der Größe n ) sind Konjugate, wenn die Permutationen g und g -1 (auch der Größe n ) so sind, dass

x = gyg-1

und gg -1 ist gleich der Identitätspermutation (die ersten n Zahlen in der richtigen Reihenfolge).

Ihre Aufgabe ist es, über Standardeingabemethoden zwei gleich große Permutationen zu nehmen und zu entscheiden, ob es sich um Konjugate handelt. Sie sollten einen von zwei konsistenten Werten ausgeben, einen, wenn es sich um Konjugate handelt, und den anderen, wenn dies nicht der Fall ist.

Dies ist Codegolf, daher werden die Antworten in Bytes bewertet, wobei weniger Bytes besser sind.

Es gibt viele Theoreme über konjugierte Permutationen, die Ihnen zur Verfügung stehen, also viel Glück und glückliches Golfen.

Sie können Eingaben als einen geordneten Container mit Werten (entweder 1-n oder 0-n) annehmen, die die Permutation wie oben darstellen, oder als eine Funktion, die einen geordneten Container annimmt und die Permutation ausführt. Wenn Sie die Funktion übernehmen möchten, sollten Sie sie als Argument verwenden, anstatt sie unter einem vordefinierten Namen zu haben.

Testfälle

(1) (1) -> True
(1 2) (2 1) -> False
(2 1) (2 1) -> True
(4 1 3 2) (4 2 1 3) -> True
(3 2 1 4) (4 3 2 1) -> False 
(2 1 3 4 5 7 6) (1 3 2 5 4 6 7) -> True
code-golf decision-problem combinatorics permutations abstract-algebra Weizen-Assistent
quelle
Können wir Eingaben als Funktion nehmen? Können wir auch die Größe n aufnehmen?
Xnor
@ xnor Sicher in beiden Punkten. Ich bin mir nicht sicher, wie der erste dir helfen wird.
Weizen-Assistent
Nach den Standardregeln für die Funktionseingabe kann davon ausgegangen werden, dass die Funktion vordefiniert ist, wodurch Bytes beim Schreiben als Argument eingespart werden, sofern Sie dies zulassen.
Xnor
@xnor Sprechen wir über diese Regel? Das ist für Black-Box-Funktionen, die Permutationen nicht sind. Dies ist sinnvoll, da dieser Konsens darauf ausgelegt ist, dass Sprachen ohne Funktionszeiger / -objekte miteinander konkurrieren können, wohingegen dies hier möglich ist, da Permutationen auf andere Weise dargestellt werden können.
Weizen-Assistent
Ich dachte nicht daran, dass es sich bei ihnen um Blackbox handelt. Die Eingabe kann also hier eine Funktion sein, aber nur als explizites Argument?
16.

Antworten:

6

Python 2 , 87 Bytes

f=lambda P,k:k<1or len({sum([x==eval('L['*k+'x'+']'*k)for x in L])for L in P})&f(P,k-1)

Probieren Sie es online!

Nimmt Eingaben mit Pals Paar beider Permutationen und kihrer Länge. Ausgänge 1für Konjugate und 0nicht.

Dies verwendet das Ergebnis:

Zwei Permutationen x und y sind genau dann konjugiert, wenn ihre k- ten Potenzen x k und y k für jedes k von 0 bis n die gleiche Anzahl von Fixpunkten haben .

Zwei konjugierte Permutationen erfüllen dies, weil ihre k- ten Potenzen ebenfalls konjugiert sind und die Konjugation die Anzahl der Fixpunkte beibehält.

Es ist weniger offensichtlich, dass sich zwei nicht konjugierte Permutationen immer unterscheiden. Insbesondere wird die Konjugation durch die sortierte Liste der Zykluslängen bestimmt, und diese können aus den Zählwerten der festen Punkte gewonnen werden. Eine Möglichkeit, dies zu zeigen, ist die lineare Algebra, auch wenn es zu viel des Guten ist.

Sei X die Permutationsmatrix für x . Dann wird die Anzahl von Fixpunkten von x k ist Tr (X k ) . Diese Kurven sind die leistungssummensymmetrischen Polynome der Eigenwerte von X k mit Multiplizität. Diese Polynome für k von 0 bis n geben die entsprechenden elementaren symmetrischen Polynome dieser Eigenwerte und damit das charakteristische Polynom und damit die Eigenwerte selbst wieder.

Da diese Eigenwerte Wurzeln der Einheit sind, die den Zyklen von x entsprechen , können wir aus diesen die Zyklusgrößen und ihre Multiplizitäten gewinnen. Unsere "Signatur" identifiziert also die Permutation bis zur Konjugation.

xnor
quelle
6

J , 25 Bytes 23 Bytes 16 Bytes

Meilen ' stillschweigende Lösung:

-:&([:/:~#&>)&C.

Die explizite Lösung von OP:

c=:4 :'-://:~"1#&>C.&>x;y'

Hiermit wird geprüft, ob die Permutationen x und y den gleichen Zyklustyp haben. Dabei wird die integrierte C.Funktion verwendet, um Zyklusdarstellungen zu erstellen.

   4 1 3 2   c   4 2 1 3
1
   3 2 1 4   c   4 3 2 1
0
   2 1 3 4 5 7 6   c   1 3 2 5 4 6 7
1
Mathias Dolidon
quelle
1
Willkommen bei PPCG und schönen ersten Beitrag. Ich habe Ihre Methode -:&([:/:~#&>)&C.mit einer stillschweigenden Form auf 16 Bytes verkürzt . Hier ist ein TIO- Link, um es auszuprobieren.
Meilen
Vielen Dank. :) Ich bin noch ein ziemlicher J-Anfänger, und obwohl ich es mit expliziten Formularen leicht zu gebrauchen scheine, erfordert das Verfassen effizienter stillschweigender Formulare immer noch viel Nachdenken für mich. Ich werde Ihre Lösung hinzufügen.
Mathias Dolidon
PS: Zählen wir nicht auch die Zeichen der Funktionszuweisungen? c=:
Mathias Dolidon
1
@MathiasDolidon Nein, standardmäßig werden die für die Zuweisung erforderlichen Zeichen nicht gezählt, da die Funktion unverändert verwendet werden kann (mit Klammern, aber nicht gezählt).
Erik der Outgolfer
1
IN ORDNUNG ! Ich habe die Zählungen für die explizite Lösung im Titel rückwirkend aktualisiert, um dies zu berücksichtigen.
Mathias Dolidon
4

MATL , 20 19 17 16 Bytes

xY@!"&G@)@b)X=va

Eingabe: zwei Spaltenvektoren ( ;als Trennzeichen verwenden). Ausgabe: 1Wenn konjugiert, 0wenn nicht.

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

Keine Theoreme über verwendete Permutationen (aus purer Unwissenheit); nur rohe Gewalt und diese beiden Fakten:

  • Für zwei Permutationen p und q entspricht die Zusammensetzung pq der Verwendung von p zum Indizieren der Elemente von q .

  • Die Bedingung x = gyg −1 entspricht xg = gy .

Kommentierter Code:

x      % Implicitly input first permutation, x. Delete it. Gets copied into clipboard G
Y@     % Implicitly input second permutation, y. Push a matrix with all permutations
       % of its elements, each permutation on a different row. So each matrix row is
       % a permutation of [1 2 ...n], where n is the size of y
!      % Transpose. Now each permutation is a column
"      % For each column
  &G   %   Push x, then y
  @    %   Push current column. This is a candidate g permutation
  )    %   Reference indexing. This gives g composed with y
  @    %   Push current column again
  b    %   Bubble up. Moves x to the top of the stack
  )    %   Reference indexing. This gives x composed with g
  X=   %   Are they equal as vectors? Gives true or false
  v    %   Concatenate stack so far. The stack contains the latest true/false result
       %   and possibly the accumulated result from previous iterations
  a    %   Any: gives true if any element is true. This is the "accumulating" function
       % Implicit end. Implicit display
Luis Mendo
quelle
2

Jelly , 11 Bytes

Œ!©Ụ€ịị"®⁸e

Probieren Sie es online!

Wie es funktioniert

Œ!©Ụ€ịị"®⁸e  Main link. Left argument: x. Right argument: y

Œ!©          Take all permutations g of x. Copy the result to the register.
   Ụ€        Grade up each; sort the indices of each permutation g by their
             corresponding values. For permutations of [1, ..., n], grading up
             essentially computes the inverse, g⁻¹.
     ị       Let each g⁻¹ index into y, computing g⁻¹y.
      ị"®    Let the results index into the corresponding g, computing g⁻¹yg.
         ⁸e  Test if x occurs in the result.
Dennis
quelle
Soweit ich weiß, sind es tatsächlich ydie Indizes, die sich ineinander einfügen g⁻¹und nicht umgekehrt. Siehe das Beispiel (4 1 2 3)(2 1 3 4) = (4 2 1 3). Bei Ihrer Vorgehensweise würde dies (1 4 2 3)stattdessen dazu führen, dass die zweite in die erste indiziert wird. Unter Berücksichtigung dessen habe ich eine 12-Byte-Lösung, die ich noch nicht verderben werde. :-)
Erik der Outgolfer
@EriktheOutgolfer Behoben.
Dennis
@Dennis Aber ich bin aufgrund der Erklärung nicht zu dem Schluss gekommen, dass ich genau den gleichen Ansatz gewählt habe, mit der Ausnahme, dass ich etwas Ähnliches hatte Œ!©Ụ€⁹ịЀ®ị"⁸e(im Grunde alle Indizierungen mit umgekehrten Argumenten), mit Ausnahme von Kürzeren, nachdem ich größere Änderungen vorgenommen hatte. Ich denke nicht g⁻¹ygdasselbe wie gyg⁻¹. Ich denke, Ihre Antwort kann auch von diesen Änderungen profitieren, aber wie ich bereits sagte, möchte ich den Spaß noch nicht ruinieren.
Erik der Outgolfer
Ja, es ist genau das gleiche. Wenn x = g⁻¹yg, dann gxg⁻¹ = y, so xund yist Konjugate.
Dennis
Hm, ich habe das Gefühl, ich sollte dann meine 12-Byte-Lösung enthüllen:eŒ!ị"Ụị@¥€¥¥
Erik the Outgolfer
1

Schale , 9 Bytes

¤¦ṠmöLU¡!

Gibt 1für konjugiert und 0für nicht konjugiert zurück. Probieren Sie es online!

Erläuterung

Die Konjugationsklasse einer Permutation P von L = [1,2, .., n] wird durch das Multiset bestimmt, das die kleinste Periode jeder Zahl in L unter P enthält . Wenn P im Listenformat genommen wird, kann ich L durch P ersetzen und das gleiche Multiset erhalten. Das Programm berechnet für jeden Eingang das entsprechende Multiset und prüft, ob eines ein Sub-Multiset des anderen ist. Da sie die gleiche Anzahl von Elementen haben, entspricht dies dem gleichen Multiset.

¤¦ṠmöLU¡!  Implicit inputs: two lists of integers.
¤          Apply one function to both and combine with another function.
  ṠmöLU¡!  First function. Argument: a list P.
  Ṡm       Map this function over P:
       ¡!  iterate indexing into P,
      U    take longest prefix with unique elements,
    öL     take its length.
 ¦         Combining function: is the first list a subset of the other, counting multiplicities?
Zgarb
quelle
1

Perl, 61 58 57 Bytes

Beinhaltet +2fürap

Geben Sie 0-basierte Permutationen als 2 Zeilen in STDIN an

perl -ap '$_=[@1]~~[@1=map{-grep$_-$G[$i++%@G],@F=@G[@F]}@G=@F,0]'
3 0 2 1
3 1 0 2
^D

Der Algorithmus ist eine geringfügige Abweichung von dem in xnors Lösung

Diese ältere Version des Codes stößt auf einen Perl-Fehler und löscht den Kern für mehrere Eingaben in meiner neuesten Perl-Version 5.26.1, funktioniert jedoch in einer älteren Perl- Version 5.16.3.

@{$.}=map{-grep$_==$F[$i++%@F],@G=@F[@G]}@G=@F,0}{$_=@1~~@2

Es ist möglicherweise ein weiteres Beispiel für meinen alten Perlgolf-Feind, die Tatsache, dass Perl seinen Stapel nicht richtig zählt.

Tonne Hospel
quelle
1

JavaScript (ES6), 66 64 Bytes

(a,b,g=a=>b+a.map(h=(e,i)=>e-i&&1+h(a[e],i)).sort())=>g(a)==g(b)

Wenn ich die anderen Antworten richtig gelesen habe, ist das Problem gleichbedeutend mit dem Zählen der Perioden aller Elemente und dem Überprüfen, ob die beiden Listen die gleiche Nummer für jede Periode haben. Bearbeiten: 1 Byte dank @Arnauld gespeichert, indem ein Byte weniger als der Zeitraum berechnet wurde. Dank @Arnauld konnte ein weiteres Byte gespart werden, indem die seltsamen Zwangsregeln von JavaScript zum Vergleichen der Arrays missbraucht wurden. Ein weiteres Byte könnte durch Curry gespeichert werden, aber ich mag kein Curry, es sei denn, es ist Chicken Tikka Masala.

Neil
quelle