ZADANIE

DEFINICJE

Rozważ punkty {1,2,3,4,5} i wszystkie ich permutacje. Możemy znaleźć całkowitą liczbę możliwych permutacji tych 5 punktów za pomocą prostej sztuczki: Obrazowanie wypełnia 5 miejsc tymi punktami, pierwsze miejsce będzie miało 5 możliwych liczb, drugie 4 (ponieważ jeden został użyty do wypełnienia pierwszego miejsca) trzecia 3 i tak dalej. Zatem całkowita liczba permutacji wynosi 5 * 4 * 3 * 2 * 1; to byłoby 5! permutacje lub 120 permutacji. Możemy myśleć o tym jako o symetrycznej grupie S5, a wtedy Symmetric Group Sn miałaby n! or (n*n-1*n-2...*1)permutacje.

Permutacja „parzysta” to taka, w której występuje parzysta liczba cykli długości parzystej. Najłatwiej jest zrozumieć, kiedy napisany w notacji cyklicznej, na przykład (1 2 3)(4 5)permutacji 1->2->3->1i 4->5->4i ma jeden cykl 3 długości (1 2 3)i jeden cykl 2 długości (4 5). Podczas klasyfikowania permutacji jako nieparzystej lub nawet ignorujemy cykle nieparzystej długości i mówimy, że ta permutacja [ (1 2 3)(4 5)] jest nieparzysta, ponieważ ma nieparzystą liczbę {1} cykli o parzystej długości. Nawet przykłady:

1. (1)(2 3)(4 5)= dwa 2 długości cyklu | NAWET |
2. (1 2 3 4 5)= brak równych cykli długości | NAWET | * zauważ, że jeśli nie występują parzyste cykle długości, to permutacja jest parzysta.

Dziwne przykłady:

1. (1 2)(3 4 5)= jeden 2 cykl długości | ODD |
2. (1)(2 3 4 5)= jeden 4 cykl długości | ODD |

Jako że dokładnie połowa permutacji w dowolnej grupie symetrycznej jest parzysta, możemy nazwać grupę parzystą przemienną grupą N, więc jako S5 = 120 A5 = 60 permutacji.

NOTACJA

Permutacje powinny, przynajmniej w tym celu, być zapisywane w notacji cyklicznej, gdzie każdy cykl jest w innym nawiasie, a każdy cykl idzie w porządku rosnącym. Na przykład (1 2 3 4 5)nie (3 4 5 1 2). A w przypadku cykli z jedną liczbą, takich jak: (1)(2 3 4)(5)pojedyncze / stałe punkty można wykluczyć (1)(2 3 4)(5) = (2 3 4). Ale tożsamość {punkt, w którym wszystkie punkty są ustalone (1)(2)(3)(4)(5)} powinna być zapisana ()tylko jako reprezentacja.

WYZWANIE

Chciałbym, abyś w jak najmniejszym kodzie mógł przyjąć dowolną liczbę całkowitą dodatnią jako dane wejściowe {1,2,3,4 ...} i wyświetlić wszystkie permutacje na przemian z grupą An, gdzie n jest wartością wejściową / wszystkie parzyste permutacje Sn. Na przykład:

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

i

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)

I tak jak w przykładach, chciałbym, aby wszystkie cykle jednej długości były pomijane, a co do tożsamości: wyjścia nic, (){nie tylko nawiasów, ale z tym, czego używasz do pokazania różnych permutacji} lub idsą dopuszczalne.

DODATKOWE CZYTANIE

Więcej informacji znajdziesz tutaj:

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

POWODZENIA

A ponieważ jest to codegolf, wygrywa ten, kto może wydrukować permutacje Alternating Group An w najkrótszych bajtach.

Pyth, 26 bajtów

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.

Wypróbuj online

To rozwiązanie opiera się na zgrabnym bijectmie między permutacjami w notacji jednowierszowej a permutacjami w notacji cyklicznej. Oczywiście istnieje oczywisty bijection, w którym dwa zapisy reprezentują tę samą permutację:

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

ale to wymagałoby zbyt dużo kodu. Zamiast tego po prostu posiekaj notację jednowierszową na kawałki, zanim wszystkie liczby będą mniejsze niż wszystkie ich poprzedniki, nazwij te cykle i zbuduj z nich nową permutację.

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

Aby odwrócić ten bijection, możemy przyjąć dowolną permutację w formie cyklu, obrócić każdy cykl, aby jego najmniejsza liczba była pierwsza, posortować cykle, aby ich najmniejsze liczby pojawiały się w malejącej kolejności, i usunąć wszystkie nawiasy.

Mathematica, 84 49 31 bajtów

GroupElements@*AlternatingGroup

Kompozycja dwóch funkcji. Dane wyjściowe w postaci {Cycles[{}], Cycles[{{a, b}}], Cycles[{{c, d}, {e, f}}], ...}reprezentującej (), (a b), (c d)(e f), ....

J , 53 bajty

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

Cykle w każdej permutacji są reprezentowane jako tablice w ramkach, ponieważ J spowoduje zerowanie tablic obdartych.

Jeśli wyjście jest rozluźnione, używając 41 bajtów

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

gdzie każda permutacja może zawierać jeden cykl i zero cykli.

Stosowanie

   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││
││└─────┘│└─────┘│└───┴───┘│└─────┘│└─────┘│└─────┘│└─────┘│└───┴───┘│└─────┘│└─────┘│└───┴───┘│
└┴───────┴───────┴─────────┴───────┴───────┴───────┴───────┴─────────┴───────┴───────┴─────────┘

Dla alternatywnej realizacji

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

Galaretka , 34 28 bajtów

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

Wypróbuj tutaj .

Wyjaśnienie

Każda linia w programie Jelly definiuje funkcję; dolny to „ main”.

• Pierwszy wiersz definiuje funkcję, która sprawdza, czy iloczyn cyklu jest nieparzysty.

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

• Drugi wiersz normalizuje podział permutacji [1…n]na produkt cyklu w następujący sposób:

       µ€    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.
  

  To zmieni np . (4 3)(2 5 1)W.(1 2 5)(3 4)

Oto główny program. Pobiera argument nz wiersza poleceń i:

Œ!              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 bajtów

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]]]

Niestety 88 bajtów wystarczy, aby wygenerować przemienną grupę jako listę permutacji a, więc kosztuje mnie dodatkowe 132 130 124 123 bajty na konwersję danych wyjściowych do pożądanego formatu:

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)

Udało mi się przyciąć moją wersję ES6 do 222 216 215 bajtów:

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 bajty

Dzięki @ChristianSievers za zmniejszenie liczenia o połowę.

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

Zastosowanie w monicie:

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) ]