18
\$\begingroup\$

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

\$\endgroup\$
7
\$\begingroup\$

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)
\$\endgroup\$
2
  • \$\begingroup\$ 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:-) \$\endgroup\$ – J B Mar 11 '11 at 8:21
  • \$\begingroup\$ @JB: I was wondering why there was no JB+J here ... :) \$\endgroup\$ – Eelvex Mar 11 '11 at 8:31
4
\$\begingroup\$

Ruby - 77 chars

n,a,b=$*.map &:to_i
l=[*[*0...n].permutation]
p l.index(l[b].values_at *l[a])
\$\endgroup\$
5
  • \$\begingroup\$ Replace the last 3 lines by p l.index(l[b].values_at(*l[a])) \$\endgroup\$ – steenslag Mar 11 '11 at 0:27
  • \$\begingroup\$ Sorry for sounding rough. I meant to give advice, but I got lost in formatting problems, and apparently my editing time ran out. \$\endgroup\$ – steenslag Mar 11 '11 at 0:40
  • \$\begingroup\$ 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]. \$\endgroup\$ – Ventero Mar 11 '11 at 0:48
  • \$\begingroup\$ No problem, thanks for the advice. \$\endgroup\$ – david4dev Mar 11 '11 at 0:49
  • \$\begingroup\$ @Ventero: I like these. [*[*0...n].permutation] made me smile. \$\endgroup\$ – steenslag Mar 11 '11 at 1:04
2
\$\begingroup\$

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

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

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.