В математике перестановка σ порядка n является биективной функцией от целых чисел 1 ... n до самой себя. Этот список:
2 1 4 3
представляет перестановку σ такую, что σ (1) = 2, σ (2) = 1, σ (3) = 4 и σ (4) = 3.
Квадратный корень перестановки σ - это перестановка, которая при применении к себе дает σ . Например, 2 1 4 3
имеет квадратный корень τ = 3 4 2 1
.
k 1 2 3 4
τ(k) 3 4 2 1
τ(τ(k)) 2 1 4 3
потому что τ ( τ (k)) = σ (k) для всех 1≤k≤n.
вход
Список из n > 0 целых чисел, все от 1 до n включительно, представляющих перестановку. Перестановка всегда будет иметь квадратный корень.
Вместо этого вы можете использовать список 0 ... n-1, если ваши входные и выходные данные согласованы.
Выход
Квадратный корень перестановки, также в виде массива.
ограничения
Ваш алгоритм должен работать за полиномиальное время по n . Это означает, что вы не можете просто пройти через все n ! перестановки порядка n .
Любые встроенные функции разрешены.
Тестовые случаи:
Обратите внимание, что многие входы имеют несколько возможных выходов.
2 1 4 3
3 4 2 1
1
1
3 1 2
2 3 1
8 3 9 1 5 4 10 13 2 12 6 11 7
12 9 2 10 5 7 4 11 3 1 13 8 6
13 7 12 8 10 2 3 11 1 4 5 6 9
9 8 5 2 12 4 11 7 13 6 3 10 1
источник
Ответы:
Perl,
124122 байтаВключает +3 для
-alp
Запустите с 1 перестановкой на основе STDIN:
rootperm.pl
:Сложность O (n ^ 3)
источник
Mathematica, 165
167байтБезымянная функция.
Semi-ungolfed:
источник
Пролог - 69 символов
Объяснение:
источник