Operación de grupo de permutación

15

Existe una biyección bien conocida entre las permutaciones de n elementos y los números 0 a n! -1, de modo que el orden lexicográfico de las permutaciones y los números correspondientes es el mismo. Por ejemplo, con 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)

También es bien sabido que las permutaciones de n elementos forman un grupo (el grupo simétrico de orden n!), Por lo que, en particular, que una permutación de n elementos aplicada a una segunda permutación de n elementos produce una permutación de n elementos .

Por ejemplo, (1, 0, 2) aplicado a (a, b, c) rinde (b, a, c), entonces (1, 0, 2) aplicado a (2, 1, 0) rinde (1, 2 , 0).

Escriba un programa que tome tres argumentos enteros: n, p1 y p2; interpreta p1 y p2 como permutaciones de n elementos; aplica el primero al segundo; y genera el entero correspondiente. Por ejemplo:

$ ./perm.sh 3 2 5
3
Peter Taylor
fuente

Respuestas:

7

J, 30

Me gusta la elegancia de esto:

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

o esto:

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

pero funcionan así:

3 f 2 5
3
12 f 8 9
17

Entonces esta es la entrada válida:

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

Algunas explicaciones:

  • 3 A. 0 1 2: da la tercera permutación de 0 1 2(= 1 2 0)
  • 0 1 2 (A.)~ 3: es lo mismo pero con argumentos invertidos
  • 0 1 2 (A.)~/ 3 4 5 ..."aplica" (A.)~a 3 4 5 ..., por lo que da la 3ra, 4ta, 5ta, ... permutación de 0 1 2.
  • A. 1 2 0: da el orden de la permutación de 1 2 0(= 3)
  • i. n: da la secuencia 0 1 2 ... n-1
  • 1 2 0 { 0 2 1organiza 0 2 1por 1 2 0(= 2 1 0)
Eelvex
fuente
Buen trabajo. Le eché un vistazo a la documentación de A.ayer, pero estaba demasiado cansada para intentar reunirla en el orden correcto para la pregunta O :-)
JB
@JB: Me preguntaba por qué no había JB + J aquí ... :)
Eelvex
4

Ruby - 77 caracteres

n,a,b=$*.map &:to_i
l=[*[*0...n].permutation]
p l.index(l[b].values_at *l[a])
david4dev
fuente
Reemplace las últimas 3 líneas por p l.index (l [b] .values_at (* l [a]))
steenslag
Perdón por sonar rudo. Tenía la intención de dar consejos, pero me perdí en problemas de formato, y aparentemente mi tiempo de edición se agotó.
steenslag
ARGV.map{|x|x.to_i}-> $*.map &:to_iguarda otros pocos caracteres. Y puede reemplazar la segunda línea con l=[*[*0...n].permutation].
Ventero
No hay problema, gracias por el consejo.
david4dev
@Ventero: Me gustan estos. [* [* 0 ... n] .permutation] me hizo sonreír.
steenslag
2

Python 2.6, 144 caracteres

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))
Keith Randall
fuente