A TAREFA

DEFINIÇÕES

Considere os pontos {1,2,3,4,5} e todas as suas permutações. Podemos encontrar o número total de permutações possíveis desses 5 pontos com um truque simples: Criação de imagens preenchendo 5 slots com esses pontos, o primeiro slot terá 5 números possíveis, o segundo 4 (como um foi usado para preencher o primeiro slot) o terceiro 3 e assim por diante. Assim, o número total de permutações é 5 * 4 * 3 * 2 * 1; isso seria 5! permutações ou 120 permutações. Podemos pensar nisso como o grupo simétrico S5, e então o grupo simétrico Sn teria n! or (n*n-1*n-2...*1)permutações.

Uma permutação "par" é aquela em que existe um número par de ciclos de comprimento par. É mais fácil de compreender quando escrito em notação cíclico, por exemplo, (1 2 3)(4 5)permuta-se 1->2->3->1e 4->5->4e tem um ciclo de 3 comprimento (1 2 3)e um ciclo de 2 comprimento (4 5). Ao classificar uma permutação como ímpar ou par, ignoramos os ciclos de comprimento ímpares e dizemos que essa permutação [ (1 2 3)(4 5)] é ímpar, pois possui um número ímpar {1} de ciclos de comprimento par. Mesmo exemplos:

1. (1)(2 3)(4 5)= dois ciclos de 2 comprimentos | MESMO |
2. (1 2 3 4 5)= sem ciclos de comprimento uniforme | MESMO | * observe que, se não houver ciclos de comprimento iguais, a permutação será uniforme.

Exemplos ímpares:

1. (1 2)(3 4 5)= um ciclo de 2 comprimentos | ODD
2. (1)(2 3 4 5)= um ciclo de 4 comprimentos | ODD

Como exatamente metade das permutações em qualquer grupo simétrico são iguais, podemos chamar o grupo par de Grupo Alternativo N, assim como S5 = 120 A5 = 60 permutações.

NOTAÇÃO

As permutações devem, pelo menos para isso, ser escritas em notação cíclica, onde cada ciclo está entre parênteses diferentes e cada ciclo segue em ordem crescente. Por exemplo, (1 2 3 4 5)não (3 4 5 1 2). E para ciclos com um único número, como: (1)(2 3 4)(5)os pontos únicos / fixos podem ser excluídos (1)(2 3 4)(5) = (2 3 4). Mas a identidade {o ponto em que todos os pontos são fixos (1)(2)(3)(4)(5)} deve ser escrita como ()apenas para representá-la.

O DESAFIO

Gostaria que você, no menor código possível, pegue qualquer número inteiro positivo como entrada {1,2,3,4 ...} e exiba todas as permutações do Grupo Alternativo An onde n é a entrada / todos os pares permutações de Sn. Por exemplo:

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

e

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)

E, como nos exemplos, eu gostaria que todos os ciclos de um comprimento fossem eliminados, e quanto à identidade: saídas de nada, (){não apenas entre parênteses, mas com o que você estiver usando para mostrar permutações diferentes} ou idseja aceitável.

LEITURA EXTRA

Você pode encontrar mais informações aqui:

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

BOA SORTE

E como esse é o codegolf, quem pode imprimir as permutações do Alternating Group An nos bytes mais curtos ganha.

Pitão, 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.

Experimente online

Esta solução é baseada em uma bijeção pura entre permutações na notação de uma linha e permutações na notação de ciclo. Obviamente, existe a bijeção óbvia em que as duas notações representam a mesma permutação:

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

mas isso exigiria muito código. Em vez disso, basta cortar a notação de uma linha em pedaços antes de todos os números menores que todos os seus predecessores, chamar esses ciclos de pedaços e criar uma nova permutação a partir deles.

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

Para reverter essa bijeção, podemos fazer qualquer permutação na forma de ciclo, girar cada ciclo para que seu menor número seja o primeiro, classificar os ciclos para que seus menores números apareçam em ordem decrescente e apagar todos os parênteses.

Mathematica, 84 49 31 bytes

GroupElements@*AlternatingGroup

Composição de duas funções. Saídas no formulário {Cycles[{}], Cycles[{{a, b}}], Cycles[{{c, d}, {e, f}}], ...}representando (), (a b), (c d)(e f), ....

J , 53 bytes

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

Os ciclos em cada permutação são representados como matrizes in a box, pois J irá zerar as matrizes irregulares.

Se a saída estiver relaxada, use 41 bytes

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

onde cada permutação pode conter um ciclo e zero.

Uso

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

Para a implementação alternativa,

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

Geléia , 34 28 bytes

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

Experimente aqui .

Explicação

Cada linha em um programa Jelly define uma função; o inferior é " main".

• A primeira linha define uma função que testa se um produto de ciclo é ímpar.

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

• A segunda linha normaliza uma partição de uma permutação de [1…n]em um produto de ciclo da seguinte maneira:

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

  Isso se transformará, por exemplo, (4 3)(2 5 1)em (1 2 5)(3 4).

Aqui está o programa principal. Ele recebe um argumento nda linha de comando e:

Œ!              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 bytes

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

Infelizmente, 88 bytes são suficientes para gerar o grupo alternativo como uma lista de permutações de a, portanto, isso me custa um adicional de 132 130 124 123 123 bytes para converter a saída no formato desejado:

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)

Consegui reduzir minha versão do ES6 para 222 216 215 bytes:

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

Obrigado a @ChristianSievers por reduzir a contagem ao meio.

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

Uso no prompt:

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