LA TAREA

Definiciones

Considere los puntos {1,2,3,4,5} y todas sus permutaciones. Podemos encontrar el número total de permutaciones posibles de estos 5 puntos con un simple truco: imágenes que llenan 5 espacios con estos puntos, el primer espacio tendrá 5 números posibles, el segundo 4 (como se ha usado uno para llenar el primer espacio) los terceros 3 y así sucesivamente. Por lo tanto, el número total de permutaciones es 5 * 4 * 3 * 2 * 1; esto sería 5! permutaciones o 120 permutaciones. Podemos pensar en esto como el grupo simétrico S5, y luego el grupo simétrico Sn tendría n! or (n*n-1*n-2...*1)permutaciones.

Una permutación "par" es aquella en la que hay un número par de ciclos de longitud par. Es más fácil de entender cuando se escribe en notación cíclico, por ejemplo (1 2 3)(4 5)permuta 1->2->3->1y 4->5->4y tiene un ciclo de 3 longitud (1 2 3)y un ciclo de 2 longitud (4 5). Al clasificar una permutación como impar o par, ignoramos los ciclos de longitud impar y decimos que esta permutación [ (1 2 3)(4 5)] es impar ya que tiene un número impar {1} de ciclos de longitud par. Incluso ejemplos:

1. (1)(2 3)(4 5)= dos ciclos de 2 longitudes | INCLUSO |
2. (1 2 3 4 5)= sin ciclos de longitud par | INCLUSO | * tenga en cuenta que si no hay ciclos de longitud par, entonces la permutación es par.

Extraños ejemplos:

1. (1 2)(3 4 5)= un ciclo de 2 longitudes | ODD |
2. (1)(2 3 4 5)= un ciclo de 4 longitudes | ODD |

Como exactamente la mitad de las permutaciones en cualquier grupo simétrico son pares, podemos llamar al grupo par el grupo alterno N, de modo que S5 = 120 A5 = 60 permutaciones.

NOTACIÓN

Las permutaciones deben, al menos para esto, escribirse en notación cíclica donde cada ciclo está en paréntesis diferente y cada ciclo va en orden ascendente. Por ejemplo (1 2 3 4 5)no (3 4 5 1 2). Y para los ciclos con un solo número, como: (1)(2 3 4)(5)los puntos únicos / fijos pueden excluirse del significado (1)(2 3 4)(5) = (2 3 4). Pero la identidad {el punto donde se fijan todos los puntos (1)(2)(3)(4)(5)} debe escribirse ()solo para representarla.

EL RETO

Me gustaría que, en el menor código posible, tome cualquier número entero positivo como entrada {1,2,3,4 ...} y muestre todas las permutaciones del Grupo Alternador An donde n es la entrada / todo el par permutaciones de Sn. Por ejemplo:

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

y

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)

Y al igual que en los ejemplos, me gustaría que se elidieran todos los ciclos de una longitud, y en cuanto a la identidad: salidas de nada, (){no solo corchetes sino con lo que sea que esté usando para mostrar diferentes permutaciones} o idsean aceptables.

LECTURA EXTRA

Puedes encontrar más información aquí:

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

BUENA SUERTE

Y como se trata de codegolf, cualquiera que pueda imprimir las permutaciones del Grupo An alternado en los bytes más cortos gana.

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.

Pruébalo en línea

Esta solución se basa en una biyección ordenada entre permutaciones en notación de una línea y permutaciones en notación de ciclo. Por supuesto, está la biyección obvia donde las dos notaciones representan la misma permutación:

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

pero eso tomaría demasiado código. En cambio, simplemente corta la notación de una línea en pedazos antes de todos los números que son más pequeños que todos sus predecesores, llama a estos ciclos de piezas y construye una nueva permutación a partir de ellos.

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

Para revertir esta biyección, podemos tomar cualquier permutación en forma de ciclo, rotar cada ciclo para que su número más pequeño sea el primero, ordenar los ciclos para que sus números más pequeños aparezcan en orden decreciente y borrar todos los paréntesis.

Mathematica, 84 49 31 bytes

GroupElements@*AlternatingGroup

Composición de dos funciones. Salidas en la forma que {Cycles[{}], Cycles[{{a, b}}], Cycles[{{c, d}, {e, f}}], ...}representa (), (a b), (c d)(e f), ....

J , 53 bytes

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

Los ciclos en cada permutación se representan como matrices en recuadro, ya que J rellenará con cero las matrices irregulares.

Si la salida es relajada, usando 41 bytes

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

donde cada permutación puede contener ciclos de uno y cero ciclos.

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 la implementación alternativa,

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

Jalea , 34 28 bytes

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

Pruébalo aquí .

Explicación

Cada línea en un programa Jelly define una función; el inferior es " main".

• La primera línea define una función que prueba si un producto de ciclo es impar.

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

• La segunda línea normaliza una partición de una permutación [1…n]en un producto de ciclo de la siguiente manera:

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

  Esto se convertirá, por ejemplo, (4 3)(2 5 1)en (1 2 5)(3 4).

Aquí está el programa principal. Toma un argumento nde la línea de comando y:

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

Lamentablemente, 88 bytes solo son suficientes para generar el grupo alterno como una lista de permutaciones de a, por lo que luego me cuesta 132 130 124 123 bytes adicionales para convertir la salida al formato deseado:

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)

Me las arreglé para recortar mi versión ES6 a 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

Gracias a @ChristianSievers por reducir el recuento a la mitad.

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

Uso en el indicador:

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