14
\$\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, p1, and p2; interprets p1 and p2 as permutations of n elements; applies the first to the second; and outputs the corresponding integer. For example:

$ ./perm.sh 3 2 5
3
\$\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\$
  • \$\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\$
  • \$\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\$

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.