9
\$\begingroup\$

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:

GOOD LUCK

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

\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to Programming Puzzles and Code Golf! Normally, we allow the output to be flexible, so that languages which have problems with outputting in the right format don't have an unfair disadvantage. Is it allowed to output for example [[1, 2], [3, 4]] instead of (1 2)(3 4)? \$\endgroup\$ – Adnan Jul 3 '16 at 0:18
  • \$\begingroup\$ @Adnan Yes, I should've clarified. As long as the different cycles are shown separately there should be no problem with how you have represented this. \$\endgroup\$ – Harry Jul 3 '16 at 6:43
  • \$\begingroup\$ "An "even" permutation is one where there is an even number of even permutations." This looks like a cyclic definition. Maybe introduce cycle notation first and then rewrite that sentence to "... even number of even-length cycles"? \$\endgroup\$ – Martin Ender Jul 3 '16 at 8:17
  • \$\begingroup\$ Also, how do I put the cycle (2 3 1 4) in ascending order? Do you mean we should just put the smallest element at the front? \$\endgroup\$ – Martin Ender Jul 3 '16 at 8:19
  • \$\begingroup\$ @MartinEnder Yes the smallest element should go first as long as it doesn't mess with the order, so as (2 3 1 4) does 2->3->1->4->2 it can be written (1 4 2 3) with its smallest element first \$\endgroup\$ – Harry Jul 3 '16 at 8:26
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The OP requires the identity permutation to be represented without one-cycles. I do think it'd be better if it weren't the case. \$\endgroup\$ – miles Jul 3 '16 at 22:59
  • 1
    \$\begingroup\$ Harry seemed to okay my Jelly answer, which prints 1-cycles even for id. Maybe he could chime in? \$\endgroup\$ – Lynn Jul 3 '16 at 23:01
  • \$\begingroup\$ I'm not so sure too with the way it's worded, and I didn't notice that your (Lynn's) solution did the same too. \$\endgroup\$ – miles Jul 3 '16 at 23:07
  • \$\begingroup\$ My understanding was that you couldn't represent the identity permutation using the empty string, so I amended my answer to keep all the 1-cycles (also conveniently saving 6 bytes). \$\endgroup\$ – Neil Jul 4 '16 at 8:28
  • 1
    \$\begingroup\$ I have edited my question to be more clear, I would like the "one cycles" to be elided as you have done in the second part of your answer. Well done by the way. \$\endgroup\$ – Harry Jul 4 '16 at 15:25
6
\$\begingroup\$

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), ....

\$\endgroup\$
3
\$\begingroup\$

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│ │ │
└─────┴─┴─┘
\$\endgroup\$
  • \$\begingroup\$ This is actually beautiful... well done. \$\endgroup\$ – Harry Jul 3 '16 at 7:56
2
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ I tried running it with 5 as an input, and got no output at all. Is this script for just Groups A3 and A4 or can it potentially give any group? I have never even seen Jelly before so any explanation would be helpful. \$\endgroup\$ – Harry Jul 3 '16 at 18:21
  • \$\begingroup\$ No I only put 3 and 4 in the challange so, so far you are winning but I really just want to learn more. \$\endgroup\$ – Harry Jul 3 '16 at 18:30
  • \$\begingroup\$ Jelly actually has a built-in for partitions, which I forgot about! Thankfully, a friend reminded me. So now it’s more efficient (handles n=5, yay!) and shorter. \$\endgroup\$ – Lynn Jul 3 '16 at 20:54
  • \$\begingroup\$ OP has edited the question to clarify that 1-cycles must be elided. \$\endgroup\$ – Anders Kaseorg Jul 4 '16 at 22:17
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I don't mind if the format is not in perfect cyclic notation as long as: each permutation and its cycles are shown separate ( like [1 2 3][4 5] and <<123><45>> would both be acceptable) and cycles of one length are elided. Perhaps this can shorten your answer \$\endgroup\$ – Harry Jul 4 '16 at 15:33
  • \$\begingroup\$ @Harry I'd never show (1,2,3)(4,5) - that's an odd permutation! Currently I'd show e.g. (1,2,3)(4)(5) - not only does removing cycles of length one cost me 6 bytes I then end up with an empty result for the identity cycle which would cost me another 4 bytes to fix. \$\endgroup\$ – Neil Jul 4 '16 at 16:38
  • \$\begingroup\$ If you mean nothing is printed for the identity then I will accept that as I said as for the identity outputs of nothing ... are accepatble. And also what would be shown if you output your "raw data", does it come in the form (1,2,3)(4)(5) or as something else? \$\endgroup\$ – Harry Jul 4 '16 at 16:43
  • \$\begingroup\$ @Harry Now excluding cycles of length one, including a blank entry for the identity, and still managing to save a byte! \$\endgroup\$ – Neil Jul 4 '16 at 20:05
  • \$\begingroup\$ @Harry Raw data would be [1, 2, 0, 3, 4] for that particular example, so nowhere near what you want. \$\endgroup\$ – Neil Jul 4 '16 at 20:07
1
\$\begingroup\$

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) ]
\$\endgroup\$
  • \$\begingroup\$ Very nice formatting, I think GAP was a very good choice for answering this problem. \$\endgroup\$ – Harry Jul 4 '16 at 14:57
  • \$\begingroup\$ Your answer doesn't show where one permutation ends and the next starts. Assuming the function doesn't need to print the values as a side effect, but may just return the values as a list to be printed by the interpreter, I'd do f:=n->List(AlternatingGroup(n)); \$\endgroup\$ – Christian Sievers Jul 23 '16 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.