LA TÂCHE

DÉFINITIONS

Considérez les points {1,2,3,4,5} et toutes leurs permutations. On peut trouver le nombre total de permutations possibles de ces 5 points par une simple astuce: Imaging remplissant 5 slots avec ces points, le premier slot aura 5 nombres possibles, le second 4 (comme on a été utilisé pour remplir le premier slot) le troisième 3 et ainsi de suite. Ainsi, le nombre total de permutations est de 5 * 4 * 3 * 2 * 1; ce serait 5! permutations ou 120 permutations. Nous pouvons penser à cela comme le groupe symétrique S5, puis le groupe symétrique Sn aurait des n! or (n*n-1*n-2...*1)permutations.

Une permutation "paire" est celle où il y a un nombre pair de cycles de longueur paire. Il est plus facile à comprendre lorsqu'il est écrit en notation cyclique, par exemple (1 2 3)(4 5)permute 1->2->3->1et 4->5->4et a un cycle de 3 longueur (1 2 3)et un cycle 2 de longueur (4 5). Lorsque nous classons une permutation comme impaire ou paire, nous ignorons les cycles de longueur impaires et disons que cette permutation [ (1 2 3)(4 5)] est impaire car elle a un nombre impair {1} de cycles de longueur paire. Même exemples:

1. (1)(2 3)(4 5)= deux cycles de 2 longueurs | MÊME |
2. (1 2 3 4 5)= pas de cycles de longueur pairs | MÊME | * notez que si aucun cycle de longueur paire n'est présent, alors la permutation est paire.

Exemples étranges:

1. (1 2)(3 4 5)= un cycle de 2 longueurs | ODD |
2. (1)(2 3 4 5)= un cycle de 4 longueurs | ODD |

Comme exactement la moitié des permutations dans un groupe symétrique sont paires, nous pouvons appeler le groupe pair le groupe alternatif N, de sorte que S5 = 120 A5 = 60 permutations.

NOTATION

Les permutations doivent, au moins pour cela, être écrites en notation cyclique où chaque cycle est entre parenthèses différentes et chaque cycle va dans l'ordre croissant. Par exemple (1 2 3 4 5)non (3 4 5 1 2). Et pour les cycles avec un seul numéro, tels que: (1)(2 3 4)(5)les points uniques / fixes peuvent être exclus, ce qui signifie (1)(2 3 4)(5) = (2 3 4). Mais l'identité {le point où tous les points sont fixes (1)(2)(3)(4)(5)} doit être écrite comme ()juste pour la représenter.

LE DÉFI

J'aimerais que vous, dans le moins de code possible, preniez n'importe quel entier positif comme entrée {1,2,3,4 ...} et affichez toutes les permutations du groupe alternatif An où n est l'entrée / tout le pair permutations de Sn. Par exemple:

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

et

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)

Et comme dans les exemples, je voudrais que tous les cycles d'une longueur soient élidés et que pour l'identité: sorties de rien, (){non seulement des crochets mais avec tout ce que vous utilisez pour afficher différentes permutations} ou idsont acceptables.

LECTURE SUPPLÉMENTAIRE

Vous pouvez trouver plus d'informations ici:

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

BONNE CHANCE

Et comme il s'agit de codegolf, quiconque peut imprimer les permutations du groupe alternatif An dans les octets les plus courts gagne.

Pyth, 26 octets

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.

Essayez-le en ligne

Cette solution est basée sur une bijection nette entre les permutations en notation d'une ligne et les permutations en notation de cycle. Bien sûr, il y a la bijection évidente où les deux notations représentent la même permutation:

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

mais cela prendrait trop de code. Au lieu de cela, coupez simplement la notation d'une ligne en morceaux avant tous les nombres plus petits que tous leurs prédécesseurs, appelez ces cycles de morceaux et construisez une nouvelle permutation à partir d'eux.

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

Pour inverser cette bijection, nous pouvons prendre n'importe quelle permutation sous forme de cycle, faire pivoter chaque cycle de sorte que son plus petit nombre soit le premier, trier les cycles afin que leurs plus petits nombres apparaissent dans l'ordre décroissant et effacer toutes les parenthèses.

Mathematica, 84 49 31 octets

GroupElements@*AlternatingGroup

Composition de deux fonctions. Sorties sous la forme {Cycles[{}], Cycles[{{a, b}}], Cycles[{{c, d}, {e, f}}], ...}représentant (), (a b), (c d)(e f), ....

J , 53 octets

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

Les cycles de chaque permutation sont représentés sous forme de tableaux en boîte, car J mettra à zéro les tableaux en lambeaux.

Si la sortie est détendue, en utilisant 41 octets

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

où chaque permutation peut contenir un cycle et un cycle zéro.

Usage

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

Pour la mise en œuvre alternative,

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

Gelée , 34 28 octets

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

Essayez-le ici .

Explication

Chaque ligne d'un programme Jelly définit une fonction; celui du bas est « main».

• La première ligne définit une fonction qui teste si un produit de cycle est impair.

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

• La deuxième ligne normalise une partition d'une permutation de [1…n]en un produit de cycle comme suit:

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

  Cela se transformera par exemple (4 3)(2 5 1)en (1 2 5)(3 4).

Voici le programme principal. Il prend un argument nde la ligne de commande et:

Œ!              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 212 211 octets

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

Malheureusement, 88 octets ne suffisent que pour générer le groupe alternatif sous forme de liste de permutations a, il me coûte donc 132 130 124 123 octets supplémentaires pour convertir la sortie au format souhaité:

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)

J'ai réussi à réduire ma version ES6 à 222 216 215 octets:

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 octets

Merci à @ChristianSievers d'avoir réduit de moitié le nombre.

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

Utilisation à l'invite:

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