Permutation group operation

Question

There is a well-known bijection between the permutations of \$n\$ elements and the numbers \$0\$ to \$n!-1\$ such that the lexicographic ordering of the permutations and the corresponding numbers is the same. For example, with \$n=3\$:

0 <-> (0, 1, 2)
1 <-> (0, 2, 1)
2 <-> (1, 0, 2)
3 <-> (1, 2, 0)
4 <-> (2, 0, 1)
5 <-> (2, 1, 0)

It is also well-known that the permutations of \$n\$ elements form a group (the symmetric group of order \$n!\$) - so, in particular, that one permutation of \$n\$ elements applied to a second permutation of \$n\$ elements yields a permutation of \$n\$ elements.

For example, \$(1, 0, 2)\$ applied to \$(a, b, c)\$ yields \$(b, a, c)\$, so \$(1, 0, 2)\$ applied to \$(2, 1, 0)\$ yields \$(1, 2, 0)\$.

Write a program which takes three integer arguments: \$n\$, \$p_1\$, and \$p_2\$; interprets \$p_1\$ and \$p_2\$ as permutations of \$n\$ elements via the bijection described above; applies the first to the second; and outputs the corresponding integer, reapplying the above bijection. For example:

$ ./perm.sh 3 2 5
3

This is code-golf so the shortest code in bytes wins

Answer 1

J, 30

I like the elegance of this:

[:A.[:{/]A.~/~i.@[

or this:

13 :'A.{/(i.x)(A.)~/y'

but they work like this:

3 f 2 5
3
12 f 8 9
17

So this is the valid entry:

([:A.[:{/i.@{.A.~/}.)".}.>ARGV

Some explanations:

• 3 A. 0 1 2: gives the 3rd permutation of 0 1 2 (= 1 2 0)
• 0 1 2 (A.)~ 3: is the same but with arguments reversed
• 0 1 2 (A.)~/ 3 4 5 ... "applies" (A.)~ to 3 4 5 ..., so it gives the 3rd, 4th, 5th, ... permutation of 0 1 2.
• A. 1 2 0: gives the order of the permutation of 1 2 0 (= 3)
• i. n: gives the sequence 0 1 2 ... n-1
• 1 2 0 { 0 2 1 arranges 0 2 1 by 1 2 0 (= 2 1 0)

Answer 2

Ruby - 77 chars

n,a,b=$*.map &:to_i
l=[*[*0...n].permutation]
p l.index(l[b].values_at *l[a])

Answer 3

Python 2.6, 144 chars

import sys
from itertools import*
n,p,q=map(int,sys.argv[1:])
R=range(n)
P=list(permutations(R))
print P.index(tuple(P[q][P[p][i]] for i in R))

Answer 4

Jelly, 8 bytes

œ?Ụị¥/Œ¿

Try it online!

Uses 1-indexing, Jelly's default (i.e. just increment every number in the challenge body). +2 bytes to use zero indexing. Takes \$[p_1, p_2]\$ on the left and \$n\$ on the right.

The text of the question is kinda confusing. "Applying" one permutation to another is essentially sorting the elements of the second by the values of the first, which is exactly what "grade up, then index into" does.

How it works

œ?Ụị¥/Œ¿ - Main link. Takes [p1, p2] on the left and n on the right
œ?       - Generate the permutations of [1, 2, ..., n], then yield the p1'th and p2'th values
    ¥/   - Reduce those permutations by the following, with perm(p1) on the left and perm(p2) on the right:
  Ụ      -   Grade up perm(p1); This sorts the indices of perm(p1) by their corresponding values
   ị     -   Index into perm(p2) with these sorted indices
      Œ¿ - Sort the corresponding list, get all permutations and find it's index in them