# Permutation group operation

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 so the shortest code in bytes wins ## 4 Answers ## 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) • Good job. I took a peek at the documentation for A. yesterday, but was too tired to try and assemble in the correct order for the question O:-) – J B Commented Mar 11, 2011 at 8:21 • @JB: I was wondering why there was no JB+J here ... :) Commented Mar 11, 2011 at 8:31 # Ruby - 77 chars n,a,b=$*.map &:to_i
l=[*[*0...n].permutation]
p l.index(l[b].values_at *l[a])

• Replace the last 3 lines by p l.index(l[b].values_at(*l[a])) Commented Mar 11, 2011 at 0:27
• Sorry for sounding rough. I meant to give advice, but I got lost in formatting problems, and apparently my editing time ran out. Commented Mar 11, 2011 at 0:40
• ARGV.map{|x|x.to_i} -> \$*.map &:to_i saves another few characters. And you can replace the second line with l=[*[*0...n].permutation]. Commented Mar 11, 2011 at 0:48
• No problem, thanks for the advice. Commented Mar 11, 2011 at 0:49
• @Ventero: I like these. [*[*0...n].permutation] made me smile. Commented Mar 11, 2011 at 1:04

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


# 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