# 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.

• So 0132 is Undefined Behavior?
– l4m2
Dec 26, 2022 at 10:11
• @l4m2 If you chose 0123 as the identity permutation, then no, it belongs to the last category in the list. Dec 26, 2022 at 10:13

# 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

• What does 962578>>s do though? Jan 1 at 12:48
• @DialFrost This should be read as (962578>>((s%530%13)*2))&3 : turn s into a value in 0..12, multiply it by 2, right-shift the bitmask by this amount, extract the 2 least significant bits. Jan 1 at 23:02

# 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.

# 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


# 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.

# 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.

# 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
J   -   range of length -> [1,2,3,4]
=    -   (P) equals (that) (vectorises)
S  -   sum -> Y
_     - (X) minus (Y)


# 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


# 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.

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. # 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\$$. 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\$$. 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. # 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! # 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.

# Python 3, 84 bytes

lambda s:locals().get(s[1:],3)
bcd=0


Try it online!

Essentially a port of tsh's JS answer.

# Julia 1.0, 26 24 bytes

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


Try it online!

-2 thx to @Steffan

• f(s) => !s using unary operators Jan 1 at 23:19

# Python 3, 31 bytes

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


Try it online!

# 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!

# Python 3, 105 bytes

def f(s):

Port of tsh's JS answer. Input as a string with letters a, b, c, d. Output as a number, 0 to 3.
• @KevinCruijssen thanks, I basically just copied his footer and replaced console.log with print. I didn't really check whether it was right. Dec 29, 2022 at 8:47