Print the "even" permutations of symmetric group Sn in cyclic notation

Question

THE TASK

DEFINITIONS

Consider the points {1,2,3,4,5} and all their permutations. We can find the total number of possible permutations of these 5 points by a simple trick: Imaging filling 5 slots with these points, the first slot will have 5 possible numbers, the second 4 (as one has been used to fill the first slot) the third 3 and so on. Thus the total number of Permutations is 5*4*3*2*1; this would be 5! permutations or 120 permutations. We can think of this as the symmetric group S5, and then Symmetric Group Sn would have n! or (n*n-1*n-2...*1) permutations.

An "even" permutation is one where there is an even number of even length cycles. It is easiest to understand when written in cyclic notation, for example (1 2 3)(4 5) permutes 1->2->3->1 and 4->5->4 and has one 3 length cycle (1 2 3) and one 2 length cycle (4 5). When classifying a permutation as odd or even we ignore odd length cycles and say that this permutation [(1 2 3)(4 5)] is odd as it has an odd number {1} of even length cycles. Even examples:

1. (1)(2 3)(4 5) = two 2 length cycle | EVEN |
2. (1 2 3 4 5) = no even length cycles | EVEN | * note that if no even length cycles are present then the permutation is even.

Odd Examples:

1. (1 2)(3 4 5) = one 2 length cycle | ODD |
2. (1)(2 3 4 5) = one 4 length cycle | ODD |

As exactly half of the permutations in any Symmetric Group are even we can call the even group the Alternating Group N, So as S5 = 120 A5 = 60 permutations.

NOTATION

Permutations should, for this at least, be written in cyclic notation where each cycle is in different parenthesis and each cycle goes in ascending order. For example (1 2 3 4 5) not (3 4 5 1 2). And for cycles with a single number, such as: (1)(2 3 4)(5) the single / fixed points can be excluded meaning (1)(2 3 4)(5) = (2 3 4). But the identity {the point where all points are fixed (1)(2)(3)(4)(5)} should be written as () just to represent it.

THE CHALLENGE

I would like you to, in as little code possible, take any positive integer as an input {1,2,3,4...} and display all the permutations of the Alternating Group An where n is the input / all the even permutations of Sn. For example:

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

and

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)

And as with in the examples I would like for all cycles of one length to be elided, and as for the identity: outputs of nothing, () {not only brackets but with whatever you are using to show different permutations} or id are acceptable.

EXTRA READING

You can find more information here:

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

GOOD LUCK

And as this is codegolf whoever can print the Alternating Group An's permutations in the shortest bytes wins.

Answer 1

Mathematica, 84 49 31 bytes

GroupElements@*AlternatingGroup

Composition of two functions. Outputs in the form {Cycles[{}], Cycles[{{a, b}}], Cycles[{{c, d}, {e, f}}], ...} representing (), (a b), (c d)(e f), ....

Answer 2

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.

Try it online

This solution is based on a neat bijection between permutations in one-line notation and permutations in cycle notation. Of course, there’s the obvious bijection where the two notations represent the same permutation:

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

but that would take too much code. Instead, simply chop the one-line notation into pieces before all numbers that are smaller than all their predecessors, call these pieces cycles, and build a new permutation out of them.

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

To reverse this bijection, we can take any permutation in cycle form, rotate each cycle so its smallest number is first, sort the cycles so that their smallest numbers appear in decreasing order, and erase all the parentheses.

Answer 3

J, 53 bytes

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

The cycles in each permutation are represented as boxed arrays since J will zero-pad ragged arrays.

If the output is relaxed, using 41 bytes

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

where each permutation may contain one-cycles and zero-cycles.

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

For the alternative implemenation,

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

Answer 4

Jelly, 34 28 bytes

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

Try it here.

Explanation

Each line in a Jelly program defines a function; the bottom one is “main”.

• The first line defines a function that tests whether a cycle product is odd.

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

• The second line normalizes a partition of a permutation of [1…n] into a cycle product as follows:

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

  This will turn e.g. (4 3)(2 5 1) into (1 2 5)(3 4).

Here is the main program. It takes an argument n from the command line, and:

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

Answer 5

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

Sadly 88 bytes only suffices to generate the alternating group as a list of permutations of a, so it then costs me an additional 132 130 124 123 bytes to convert the output to the desired format:

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)

I've managed to trim my ES6 version down to 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

Answer 6

GAP, 32 bytes

Thanks to @ChristianSievers for cutting the count in half.

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

Usage at the 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) ]