DIE AUFGABE

DEFINITIONEN

Betrachten Sie die Punkte {1,2,3,4,5} und alle ihre Permutationen. Wir können die Gesamtzahl der möglichen Permutationen dieser 5 Punkte durch einen einfachen Trick ermitteln: Stellen Sie sich vor, Sie füllen 5 Slots mit diesen Punkten, der erste Slot hat 5 mögliche Nummern, der zweite 4 (wie einer verwendet wurde, um den ersten Slot zu füllen). die dritte 3 und so weiter. Somit beträgt die Gesamtzahl der Permutationen 5 * 4 * 3 * 2 * 1; das wäre 5! Permutationen oder 120 Permutationen. Wir können uns dies als die symmetrische Gruppe S5 vorstellen, und dann hätte die symmetrische Gruppe Sn n! or (n*n-1*n-2...*1)Permutationen.

Eine "gerade" Permutation ist eine, bei der es eine gerade Anzahl von Zyklen mit gerader Länge gibt. Es ist am einfachsten zu verstehen, wenn es in zyklischer Notation geschrieben ist, zum Beispiel (1 2 3)(4 5)permutiert 1->2->3->1und 4->5->4einen 3-Längen-Zyklus (1 2 3)und einen 2-Längen-Zyklus hat (4 5). Wenn wir eine Permutation als ungerade oder gerade klassifizieren, ignorieren wir ungerade Längenzyklen und sagen, dass diese Permutation [ (1 2 3)(4 5)] ungerade ist, da sie eine ungerade Anzahl {1} ​​von geraden Längenzyklen hat. Sogar Beispiele:

1. (1)(2 3)(4 5)= zwei 2 Längenzyklen | AUCH |
2. (1 2 3 4 5)= keine geraden Längenzyklen | AUCH | * Beachten Sie, dass die Permutation gerade ist, wenn keine Zyklen mit gerader Länge vorhanden sind.

Seltsame Beispiele:

1. (1 2)(3 4 5)= ein Zyklus mit 2 Längen | ODD |
2. (1)(2 3 4 5)= ein Zyklus mit 4 Längen | ODD |

Da genau die Hälfte der Permutationen in einer symmetrischen Gruppe gerade sind, können wir die gerade Gruppe als alternierende Gruppe N bezeichnen, also als S5 = 120 A5 = 60 Permutationen.

NOTATION

Zumindest dafür sollten Permutationen in zyklischer Notation geschrieben werden, wobei jeder Zyklus in einer anderen Klammer steht und jeder Zyklus in aufsteigender Reihenfolge abläuft. Zum Beispiel (1 2 3 4 5)nicht (3 4 5 1 2). Und für Zyklen mit einer einzelnen Zahl, wie zum Beispiel: (1)(2 3 4)(5)Die einzelnen / festen Punkte können ausgeschlossen werden (1)(2 3 4)(5) = (2 3 4). Aber die Identität (der Punkt, an dem alle Punkte festgelegt sind (1)(2)(3)(4)(5)) sollte nur geschrieben werden (), um sie darzustellen.

DIE HERAUSFORDERUNG

Ich möchte, dass Sie in so wenig Code wie möglich eine positive ganze Zahl als Eingabe {1,2,3,4 ...} nehmen und alle Permutationen der alternierenden Gruppe An anzeigen, wobei n die Eingabe / alle Geraden ist Permutationen von Sn. Beispielsweise:

Input = 3
()
(1 2 3)
(1 3 2)

und

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

Und wie in den Beispielen möchte ich, dass alle Zyklen einer Länge entfernt werden, und was die Identität betrifft: Ausgaben von nichts, (){nicht nur Klammern, sondern mit allem, was Sie verwenden, um unterschiedliche Permutationen anzuzeigen} oder idakzeptabel sind.

ZUSÄTZLICHE LESUNG

Weitere Informationen finden Sie hier:

• https://en.wikipedia.org/wiki/Permutation
• https://en.wikipedia.org/wiki/Alternating_group

VIEL GLÜCK

Und da dies ein Codegolf ist, gewinnt jeder, der die Permutationen der alternierenden Gruppe An in kürzesten Bytes drucken kann.

Pyth, 26 Bytes

t#Mf%+QlT2mcdf<>dTS<dTd.pS

          m            .pSQ   Map over permutations d of [1, …, Q]:
             f        d         Find all indices T in [1, …, Q] such that
               >dT                the last Q-T elements of d
              <   S<dT            is less than the sorted first T elements of d
           cd                   Chop d at those indices
   f                          Filter on results T such that
      Q                         the input number Q
     + lT                       plus the length of T
    %    2                      modulo 2
                                is truthy (1)
t#M                           In each result, remove 0- and 1-cycles.

Probieren Sie es online aus

Diese Lösung basiert auf einer sauberen Bijektion zwischen Permutationen in Einzeilennotation und Permutationen in Zyklusnotation. Natürlich gibt es die offensichtliche Bijektion, bei der die beiden Notationen dieselbe Permutation darstellen:

[8, 4, 6, 3, 10, 1, 5, 9, 2, 7] = (1 8 9 2 4 3 6) (5 10 7)

aber das würde zu viel Code erfordern. Zerhacken Sie stattdessen einfach die einzeilige Notation vor allen Zahlen, die kleiner als alle ihre Vorgänger sind, in Teile, rufen Sie diese Teilzyklen auf und erstellen Sie daraus eine neue Permutation.

[8, 4, 6, 3, 10, 1, 5, 9, 2, 7] 8 (8) (4 6) (3 10) (1 5 9 2 7)

Um diese Bijektion umzukehren, können wir jede Permutation in Zyklusform nehmen, jeden Zyklus so drehen, dass seine kleinste Zahl an erster Stelle steht, die Zyklen so sortieren, dass ihre kleinsten Zahlen in absteigender Reihenfolge erscheinen, und alle Klammern löschen.

Mathematica, 84 49 31 Bytes

GroupElements@*AlternatingGroup

Zusammensetzung zweier Funktionen. Ausgänge in Form {Cycles[{}], Cycles[{{a, b}}], Cycles[{{c, d}, {e, f}}], ...}darstellt (), (a b), (c d)(e f), ....

J , 53 Bytes

[:(<@((>:@|.~]i.<./)&.>@#~1<#@>)@C.@#~1=C.!.2)!A.&i.]

Die Zyklen in jeder Permutation werden als Box-Arrays dargestellt, da J zerlumpte Arrays mit Null-Pad auffüllt.

Wenn die Ausgabe entspannt ist, verwenden Sie 41 Bytes

[:((1+]|.~]i.<./)&.>@C.@#~1=C.!.2)!A.&i.]

wobei jede Permutation Ein-Zyklen und Null-Zyklen enthalten kann.

Verwendungszweck

   f =: [:(<@((>:@|.~]i.<./)&.>@#~1<#@>)@C.@#~1=C.!.2)!A.&i.]
   f 3
┌┬───────┬───────┐
││┌─────┐│┌─────┐│
│││1 2 3│││1 3 2││
││└─────┘│└─────┘│
└┴───────┴───────┘
   f 4
┌┬───────┬───────┬─────────┬───────┬───────┬───────┬───────┬─────────┬───────┬───────┬─────────┐
││┌─────┐│┌─────┐│┌───┬───┐│┌─────┐│┌─────┐│┌─────┐│┌─────┐│┌───┬───┐│┌─────┐│┌─────┐│┌───┬───┐│
│││2 3 4│││2 4 3│││1 2│3 4│││1 2 3│││1 2 4│││1 3 2│││1 3 4│││1 3│2 4│││1 4 2│││1 4 3│││2 3│1 4││
││└─────┘│└─────┘│└───┴───┘│└─────┘│└─────┘│└─────┘│└─────┘│└───┴───┘│└─────┘│└─────┘│└───┴───┘│
└┴───────┴───────┴─────────┴───────┴───────┴───────┴───────┴─────────┴───────┴───────┴─────────┘

Für die alternative Implementierung

   f =: [:((1+]|.~]i.<./)&.>@C.@#~1=C.!.2)!A.&i.]
   f 3
┌─────┬─┬─┐
│1    │2│3│
├─────┼─┼─┤
│1 2 3│ │ │
├─────┼─┼─┤
│1 3 2│ │ │
└─────┴─┴─┘

Gelee , 34 28 Bytes

L€’SḂ
ṙLR$Ṃµ€Ṣ
Œ!ŒṖ€;/Ç€ÑÐḟQ

Probieren Sie es hier aus .

Erläuterung

Jede Zeile in einem Jelly-Programm definiert eine Funktion. Das unterste ist " main".

• Die erste Zeile definiert eine Funktion, die prüft, ob ein Zyklusprodukt ungerade ist.

  L€      Length of each
    ’     Add 1 to each length 
     S    Take the sum
      Ḃ   Modulo 2
  

• Die zweite Zeile normalisiert eine Partition einer Permutation [1…n]in ein Zyklusprodukt wie folgt:

       µ€    For each list X in the partition:
  ṙLR$          Rotate X by each element in [1…length(X)].
      Ṃ         Get the lexicographically smallest element.
                Thus, find the rotation so that the smallest element is in front.
         Ṣ   Sort the cycles in the partition.
  

  Dies wird zB (4 3)(2 5 1)in (1 2 5)(3 4).

Hier ist das Hauptprogramm. Es nimmt ein Argument nvon der Kommandozeile und:

Œ!              Compute all permutations of [1…n].
  ŒṖ€           Compute all partitions of each permutation.
     ;/         Put them in one big list.
       ǀ       Normalize each of them into a cycle product.
         ÑÐḟ    Reject elements satisfying the top function,
                i.e. keep only even cycle products.
            Q   Remove duplicates.

JavaScript (Firefox 30-57), 220 218 212 211 Byte

f=(a,p)=>a[2]?[for(i of a)for(j of f(a.filter(m=>m!=i),p,p^=1))[i,...j]]:[[a[p],a[p^1]]]

Leider reichen 88 Bytes nur aus, um die alternierende Gruppe als Liste von Permutationen von zu generieren. Die Konvertierung der Ausgabe in das gewünschte Format akostet mich dann zusätzlich 132 130 124 123 Bytes:

n=>f([...Array(n).keys()],0).map(a=>a.map((e,i)=>{if(e>i){for(s+='('+-~i;e>i;[a[e],e]=[,a[e]])s+=','+-~e;s+=')'}},s='')&&s)

Ich habe es geschafft, meine ES6-Version auf 222 216 215 Bytes zu reduzieren:

n=>(g=(a,p,t=[])=>a[2]?a.map(e=>g(a.filter(m=>m!=e),p,[...t,e],p^=1)):[...t,a[p],a[p^1]].map((e,i,a)=>{if(e>i){for(s+='('+-~i;e>i;[a[e],e]=[,a[e]])s+=','+-~e;s+=')'}},s='')&&r.push(s))([...Array(n).keys(r=[])],0)&&r

GAP , 32 Bytes

Vielen Dank an @ChristianSievers für die Halbierung der Anzahl.

f:=n->List(AlternatingGroup(n));

Verwendung an der Eingabeaufforderung:

gap> f(4);
[ (), (1,3,2), (1,2,3), (1,4,3), (2,4,3), (1,3)(2,4), (1,2,4), (1,4)(2,3), (2,3,4), (1,3,4), (1,2)(3,4), (1,4,2) ]