Normal Subgroups of \$S_4\$

Question

Objective

Given a permutation of 4 distinct items, classify the permutation by the normal subgroup(s) it belongs.

Input/Output Format

You gotta choose the followings as the hyperparameters for your submission:

• The 4 distinct items.

• The permutation serving as the identity permutation.

The input format is to accept a permutation of the items you chose. The items must be computably distinguishable.

The output format is flexible; you can output anything as long as the classes are computably distinguishable.

Standard loopholes apply.

In any case, an input not fitting into your format falls into don't care situation.

Classification

For example, suppose you chose the numbers 0, 1, 2, and 3 as the 4 items, and chose the string 0123 as the identity permutation.

• The identity permuation 0123 is classified as the member of the trivial group \$\textbf{0}\$.

• The permutations consisting of two non-overlapping swaps are classified as members of the Klein-four group \$K_4\$ minus the trivial group. Those are 1032, 2301, and 3210.

• The permutations that fixes exactly one item are classified as members of the alternating group \$A_4\$ minus the Klein-four group. Those are 0231, 0312, 1203, 1320, 2013, 2130, 3021, and 3102.

• The remaining permuations are classified as members of the symmetric group \$S_4\$ minus the alternating group.

Examples

Let's say you chose the string READ as the identity permutation, and chose to output the classes as numbers 0, 1, 2, and 3, respectively to the list above.

• Given the string ADER, output 3.

• Given the string ADRE, output 1.

• Given the string RADE, output 2.

• Given the string READ, output 0.

Answer 1

JavaScript (ES6), 23 bytes

Expects a permutation of the string "4567" and returns 0 ... 3.

s=>962578>>s%530%13*2&3

Try it online!

How?

Below is a view of the lookup bitmask and where each possible input is mapped once the expression \$(n \bmod 530)\bmod 13\$ is applied.

00 00 11 10 10 11 00 00 00 01 00 10
11 10  9  8  7  6  5  4     2  1  0
 |  |  |  |  |  |  |  |     |  |  |
 |  |  |  |  |  |  |  |     |  |  +--> 7654
 |  |  |  |  |  |  |  |     |  +-----> 4657, 7564
 |  |  |  |  |  |  |  |     +--------> 4567
 |  |  |  |  |  |  |  +--------------> 5746, 6754, 7645
 |  |  |  |  |  |  +-----------------> 4765, 6547
 |  |  |  |  |  +--------------------> 4675, 6457, 6574, 7465
 |  |  |  |  +-----------------------> 5476
 |  |  |  +--------------------------> 6745
 |  |  +-----------------------------> 4756, 5647, 5764, 7546
 |  +--------------------------------> 5674, 7456
 +-----------------------------------> 4576, 5467, 6475

Answer 2

Python NumPy, 26 bytes

lambda A:(2*A-A@A).trace()

Attempt This Online!

Uses as the four distinct items the vectors [1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]. With this convention the input, conveniently, becomes a permutation matrix.

Outputs 2 x # fixed points A - # fixed points AA. This maps the identity to 4, the rest of the Klein four group to -4, the rest of the alternating group to 1 and everything else to 0.

Python, 48 bytes

lambda A:sum(2*(A[a]==a)-(A[A[a]]==a)for a in A)

Attempt This Online!

Same logic but uses items 0,1,2,3 and indexing instead of matrix operations.

Answer 3

J, 14 bytes

5|1#.2^~#@>@C.

Attempt This Online!

Found while experimenting with the cycle decomposition of each permutation.

• Category 1 (0 1 2 3) has four individual cycles of length 1.
• Category 2 (e.g. 1 0 3 2) has two cycles of length 2.
• Category 3 (e.g. 0 2 3 1) has one cycle of length 3 and another cycle of length 1.
• Category 4 (e.g. 0 1 3 2 or 1 2 3 0) has either
  • three cycles of length 1, 1, 2, or
  • a single cycle of length 4.

By squaring and summing the cycle lengths, we get

• Category 1: 4
• Category 2: 8
• Category 3: 10
• Category 4: 6 or 16

Now we can take these values modulo 5 to get 4, 3, 0, 1 for each category.

5|1#.2^~#@>@C.  Takes a permutation containing 0, 1, 2, 3
            C.  Cycle decomposition
        #@>@    Length of each cycle
     2^~        Square
  1#.           Sum
5|              Modulo 5

Answer 4

Jelly, 8 bytes

ỤƑḤ_=JSƊ

A monadic Link that accepts a permutation of [1, 2, 3, 4] and yields:

classification	output
\$e\$	-2
rest of \$K_4\$	2
rest of \$A_4\$	-1
rest of \$S_4\$	0

Try it online! Or see all cases.

How?

ỤƑḤ_=JSƊ - Link: list of integers from [1..4], P
 Ƒ       - is (P) invariant under the application of:
Ụ        -   grade-up -> 1-indexed indices sorted by value
  Ḥ      - double -> X = 2 or 0
       Ɗ - last three links as a monad - f(P):
     J   -   range of length -> [1,2,3,4]
    =    -   (P) equals (that) (vectorises)
      S  -   sum -> Y
   _     - (X) minus (Y)

Answer 5

PARI/GP, 33 bytes

p->if(permsign(p)>0,permorder(p))

Attempt This Online!

Takes input as a VecSmall of integers 1, 2, 3, 4.

If the input is an odd permutation, returns 0. Otherwise returns its order.

Answer 6

Charcoal, 22 19 bytes

§SAKS0⊘ΣＥθ⁺⁼ικ⁼ι⌕θκ

Try it online! Link is to verbose version of code. Takes input as a list of 4 integers 0..3 (+2 bytes to take input as a string of digits) and outputs a code letter 0KAS (-5 bytes to port @Albert.Lang's answer, and probably also the same length to port @JonathanAllan's answer). Explanation: Calculates the number of elements of cycle length 1 plus the number of elements of cycle length 1 or 2 (so elements of cycle length 1 get counted twice) and looks up the result.

 SAKS0              Literal string `SAKS0`
§                   Indexed by
         θ          Input list
        Ｅ           Map over elements
            ι       Current element
           ⁼        Equals
             κ      Current index
          ⁺         Plus
               ι    Current element
              ⁼     Equals
                ⌕   Index of
                  κ Current index in
                 θ  Input list
       Σ            Take the sum
      ⊘             Halved
                    Implicitly print

Cycles	Order	Sign	Length 1	Length 2	Total	Classification
1+1+1+1	1	+	4	0	8	0
2+1+1	2	-	2	2	6	S
2+2	2	+	0	4	4	K
3+1	3	+	1	0	2	A
4	4	-	0	0	0	S

• My original answer counted the number of elements of cycle length 1 and then distinguished between 2+2 and 4 by checking for an element of cycle length 2 rather than counting the number of such elements.
• @alephalpha's answer checks the sign of the permutation and returns 0 if it's - or the order if it's +.
• @Albert.Lang's answer subtracts the number of elements of cycle length 2 from the number of elements of cycle length 1.
• @JonathanAllan's answer subtracts the number of elements of cycle length 1 from 2 if the order is a factor of 2 or 0 if it is not.

Answer 7

K (ngn/k), 14 bytes

{5!#,/(x@)\'x}

Try it online!

Port of my own J solution.

The K code above executes the process a bit differently:

{5!#,/(x@)\'x}   Takes a permutation containing 0, 1, 2, 3
      (  )\'x    For each number in x, repeat and collect all values:
       x@          Index into x
   #,/           Length of flattened list
 5!              Modulo 5

Answer 8

Factor + math.combinatorics, 70 61 bytes

[ "READ"<permutations> index "0332233123322323133223313"nth ]

Try it online!

-9 bytes by using the string from corvus_192's Scala 2 answer.

Answer 9

05AB1E, 18 11 bytes

<èāQ·Iā-0¢-

-7 bytes by porting @JonathanAllan's Jelly answer, since I've been unable to find anything short myself.

[1,2,3,4] is the identity permutation. Outputs:

• -2 for this identity permutation itself;
• 2 for the three members of \$K_4\$;
• -1 for the eight members of \$A_4\$;
• 0 for the remaining twelve members of \$S_4\$.

Try it online or verify all test cases.

Explanation:

<      # Decrease each value in the (implicit) input-permutation by 1
 è     # 0-based index each into the (implicit) input-permutation
  ā    # Push a list in the range [1,length]: [1,2,3,4]
   Q   # Check if the two lists are equal
    ·  # Double this check (2 or 0)
I      # Push the input-permutation again: [z,y,x,w]
 ā     # Push list [1,2,3,4] again
  -    # Decrease the values at the same positions of the two lists: [z-1,y-2,x-3,w-4]
   0¢  # Count how many 0s are in the list (how many item were already at the correct
       # position)
-      # Subtract this amount from the earlier doubled check
       # (after which the result is output implicitly)

---

Original straight-forward approach (18 bytes):

{œIk•Lû¾hΔ>¬o∊Ì•sè

"abcd" is the identity permutation. Outputs:

• 1 for this identity permutation itself;
• 3 for the three members of \$K_4\$;
• 2 for the eight members of \$A_4\$;
• 0 for the remaining twelve members of \$S_4\$.

Try it online or verify all test cases.

Explanation:

{             # Sort the characters of the (implicit) input-permutation string
 œ            # Pop and get all its permutations
  Ik          # Pop and get the index of the input-permutation
•Lû¾hΔ>¬o∊Ì•  # Push compressed integer 100220032002200230022003
 s            # Swap so the earlier index is at the top
  è           # Index it into the the earlier integer to get a digit
              # (which is output implicitly as result)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why •Lû¾hΔ>¬o∊Ì• is 100220032002200230022003.

Answer 10

Scala 2, 61 60 bytes

s=>"033223312332232313322331"("abcd".permutations indexOf s)

Takes a permutation of "abcd" and returns an ascii digit by indexing into the given string.

Attempt This Online!

Answer 11

Haskell, 89 8 87 bytes

import Data.List
f s="033223312332232313322331"!!head(elemIndices s$permutations"abcd")

Attempt This Online!

A port of my scala answer.

Answer 12

JavaScript (Node.js), 91 bytes

s=>eval(`try{${s.slice(1)}}catch{3}`);bcd=0;adc=dab=cba=1;cdb=dbc=cad=dca=abd=bda=acb=bac=2

Try it online!

Input a string with letter "a", "b", "c", "d". Output 0~3.

Answer 13

Python 3, 84 bytes

lambda s:locals().get(s[1:],3)
bcd=0
adc=dab=cba=1
cdb=dbc=cad=dca=abd=bda=acb=bac=2

Try it online!

Essentially a port of tsh's JS answer.

Answer 14

Julia 1.0, 26 24 bytes

!s=962578>>2(s%530%13)&3

Try it online!

Port of Arnuald's JS answer.

-2 thx to @Steffan

Answer 15

Python 3, 31 bytes

lambda s:962578>>2*(s%530%13)&3

Try it online!

Port of Arnuald's JS answer.

Answer 16

Python 3, 4 bytes

Modified as suggested by lyxal in the comments to get round the functions-as-constants loophole. Possibly still cheating, since quoted text of functions still sound a lot like "complete/partial functions".

exec

Items in identity order, to be concatenated as strings and fed to the function (only difference between them is in the string literal at the end):

"(lambda x=0:(lambda y:lambda z:print((lambda p:'I'if p in'123'else'K'if p in'032 301 210'else'A'if p in'231 312 203 320 013 130 021 102'else'S')(x()+y()+z())))if isinstance(x,type(lambda:0))else'0')"

"(lambda x=0:(lambda y:lambda z:print((lambda p:'I'if p in'123'else'K'if p in'032 301 210'else'A'if p in'231 312 203 320 013 130 021 102'else'S')(x()+y()+z())))if isinstance(x,type(lambda:0))else'1')"

"(lambda x=0:(lambda y:lambda z:print((lambda p:'I'if p in'123'else'K'if p in'032 301 210'else'A'if p in'231 312 203 320 013 130 021 102'else'S')(x()+y()+z())))if isinstance(x,type(lambda:0))else'2')"

"(lambda x=0:(lambda y:lambda z:print((lambda p:'I'if p in'123'else'K'if p in'032 301 210'else'A'if p in'231 312 203 320 013 130 021 102'else'S')(x()+y()+z())))if isinstance(x,type(lambda:0))else'3')"

Try it online!

Python 3, 0 bytes

Original version. Even more cheaty, for the reason pointed out by @emanresu A in the comment (perhaps among others). But I'll leave it here for entertainment!

Items in identity order, to be concatenated and fed to the interpreter:

(lambda x=0:(lambda y:lambda z:print((lambda p:'I'if p in'123'else'K'if p in'032 301 210'else'A'if p in'231 312 203 320 013 130 021 102'else'S')(x()+y()+z())))if isinstance(x,type(lambda:0))else'0')

(lambda x=0:(lambda y:lambda z:print((lambda p:'I'if p in'123'else'K'if p in'032 301 210'else'A'if p in'231 312 203 320 013 130 021 102'else'S')(x()+y()+z())))if isinstance(x,type(lambda:0))else'1')

(lambda x=0:(lambda y:lambda z:print((lambda p:'I'if p in'123'else'K'if p in'032 301 210'else'A'if p in'231 312 203 320 013 130 021 102'else'S')(x()+y()+z())))if isinstance(x,type(lambda:0))else'2')

(lambda x=0:(lambda y:lambda z:print((lambda p:'I'if p in'123'else'K'if p in'032 301 210'else'A'if p in'231 312 203 320 013 130 021 102'else'S')(x()+y()+z())))if isinstance(x,type(lambda:0))else'3')

Output: I, K, A, S for the four cases in order.

Try it online!

Answer 17

Python 3, 159 bytes

lambda x,y:{'1032':1,'2301':1,'3210':1,'0231':2,'0312':2,'1203':2,'1320':2,'2013':2,'2130':2,'3021':2,'3102':2,'0123':0}.get(''.join(map(str,map(x.find,y))),3)

I couldn't really interpret the logic. So I went with an overkill approach.

Try it online!

Answer 18

Python 3, 105 bytes

def f(s):
 bcd=0;adc=dab=cba=1;cdb=dbc=cad=dca=abd=bda=acb=bac=2
 try:return eval(s[1:])
 except:return 3

Try it online!

Port of tsh's JS answer. Input as a string with letters a, b, c, d. Output as a number, 0 to 3.