Operação do grupo de permutação

15

Existe uma bijeção bem conhecida entre as permutações de n elementos e os números de 0 a n! -1, de modo que a ordem lexicográfica das permutações e dos números correspondentes seja a mesma. Por exemplo, com 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)

Também é sabido que as permutações de n elementos formam um grupo (o grupo simétrico de ordem n!) - portanto, em particular, que uma permutação de n elementos aplicada a uma segunda permutação de n elementos produz uma permutação de n elementos .

Por exemplo, (1, 0, 2) aplicado a (a, b, c) produz (b, a, c), então (1, 0, 2) aplicado a (2, 1, 0) produz (1, 2 0).

Escreva um programa que use três argumentos inteiros: n, p1 e p2; interpreta p1 e p2 como permutações de n elementos; aplica o primeiro ao segundo; e gera o número inteiro correspondente. Por exemplo:

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

Respostas:

7

J, 30

Eu gosto da elegância disso:

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

ou isto:

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

mas eles funcionam assim:

3 f 2 5
3
12 f 8 9
17

Portanto, esta é a entrada válida:

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

Algumas explicações:

  • 3 A. 0 1 2: dá a 3ª permutação de 0 1 2(= 1 2 0)
  • 0 1 2 (A.)~ 3: é o mesmo, mas com argumentos invertidos
  • 0 1 2 (A.)~/ 3 4 5 ..."aplica-se" (A.)~a 3 4 5 ..., então fornece a 3ª, 4ª, 5ª, ... permutação de 0 1 2.
  • A. 1 2 0: dá a ordem da permutação de 1 2 0(= 3)
  • i. n: dá a sequência 0 1 2 ... n-1
  • 1 2 0 { 0 2 1organiza 0 2 1por 1 2 0(= 2 1 0)
Eelvex
fonte
Bom trabalho. I levou uma olhada na documentação para A.ontem, mas estava cansado demais para tentar montar na ordem correta para a pergunta O :-)
JB
@JB: Eu queria saber por que não havia JB + J aqui ... :)
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
fonte
Substitua as últimas 3 linhas por p l.index (l [b] .values_at (* l [a]))
steenslag
Desculpe por parecer áspero. Eu pretendia dar conselhos, mas me perdi em problemas de formatação e, aparentemente, meu tempo de edição acabou.
11119 steelslag
ARGV.map{|x|x.to_i}-> $*.map &:to_isalva mais alguns caracteres. E você pode substituir a segunda linha por l=[*[*0...n].permutation].
Ventero 11/03/11
Não tem problema, obrigado pelo conselho.
David4dev 11/03
@ Ventero: Eu gosto disso. [* [* 0 ... n] .permutation] me fez sorrir.
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
fonte