Операция перестановочной группы

15

Существует хорошо известная биекция между перестановками n элементов и числами от 0 до n! -1, так что лексикографический порядок перестановок и соответствующих чисел одинаков. Например, при 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)

Также хорошо известно, что перестановки из n элементов образуют группу (симметрическую группу порядка n!), Поэтому, в частности, одна перестановка из n элементов, примененная ко второй перестановке из n элементов, дает перестановку из n элементов ,

Например, (1, 0, 2) применяется к (a, b, c) приводит к (b, a, c), поэтому (1, 0, 2) применяется к (2, 1, 0) приводит к (1, 2) 0).

Напишите программу, которая принимает три целочисленных аргумента: n, p1 и p2; интерпретирует p1 и p2 как перестановки n элементов; применяет первое ко второму; и выводит соответствующее целое число. Например:

$ ./perm.sh 3 2 5
3
Питер Тейлор
источник

Ответы:

7

J, 30

Мне нравится элегантность этого:

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

или это:

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

но они работают так:

3 f 2 5
3
12 f 8 9
17

Так что это действительная запись:

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

Некоторые объяснения:

  • 3 A. 0 1 2: дает 3-ю перестановку 0 1 2(= 1 2 0)
  • 0 1 2 (A.)~ 3: то же самое, но с обратными аргументами
  • 0 1 2 (A.)~/ 3 4 5 ...«относится» (A.)~к 3 4 5 ..., так что это дает 3, 4, 5, ... перестановка 0 1 2.
  • A. 1 2 0: дает порядок перестановки 1 2 0(= 3)
  • i. n: дает последовательность 0 1 2 ... n-1
  • 1 2 0 { 0 2 1организует 0 2 1по 1 2 0(= 2 1 0)
Eelvex
источник
Молодец. Я взглянул на документацию за A.вчера, но был слишком уставшим, чтобы попытаться собрать в правильном порядке вопрос O :-)
JB
@JB: Мне было интересно, почему здесь не было JB + J ... :)
Eelvex
4

Рубин - 77 символов

n,a,b=$*.map &:to_i
l=[*[*0...n].permutation]
p l.index(l[b].values_at *l[a])
оборота давид4дев
источник
Замените последние 3 строки на p l.index (l [b] .values_at (* l [a]))
steenslag
Извините за грубое звучание. Я хотел дать совет, но я заблудился в проблемах форматирования, и, видимо, мое время редактирования истекло.
Steenslag
ARGV.map{|x|x.to_i}-> $*.map &:to_iсохраняет еще несколько символов. И вы можете заменить вторую строку на l=[*[*0...n].permutation].
Вентеро
Нет проблем, спасибо за совет.
david4dev
@Ventero: мне это нравится. [* [* 0 ... n] .permutation] заставил меня улыбнуться.
Steenslag
2

Python 2.6, 144 символа

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))
Кит Рэндалл
источник