11
\$\begingroup\$

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.

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

17 Answers 17

10
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ What does 962578>>s do though? \$\endgroup\$
    – DialFrost
    Jan 1 at 12:48
  • 2
    \$\begingroup\$ @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. \$\endgroup\$
    – Arnauld
    Jan 1 at 23:02
7
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

Charcoal, 22 19 bytes

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

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
        E           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.
\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
0
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
0
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ f(s) => !s using unary operators \$\endgroup\$
    – Steffan
    Jan 1 at 23:19
1
\$\begingroup\$

Python 3, 31 bytes

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

Try it online!

Port of Arnuald's JS answer.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ @KevinCruijssen thanks, I basically just copied his footer and replaced console.log with print. I didn't really check whether it was right. \$\endgroup\$
    – The Thonnu
    Dec 29, 2022 at 8:47

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.