подсчитать количество перестановок в цикле - PullRequest
Новая
       16

подсчитать количество перестановок в цикле

0 голосов
/ 27 мая 2018

У меня есть перестановка чисел от 1 до n.в каждом ходу функция перестановки используется для сопоставления текущей перестановки с новой.

Функция определяется F(i) = p[i], которая отображает каждый элемент текущей перестановки в позицию в новой перестановке.Поскольку эта функция инъективна и сюръективна, можно доказать, что мы всегда возвращаемся к первой перестановке снова.(На самом деле это цикл в графе перестановок)

, например, [2,3,1] -> [3,1,2] -> [1,2,3] -> [2,3,1], поэтому длина цикла равна 3, поскольку первая и последняя перестановки совпадают, и мы застряли в цикле.

В качестве входных данных у меня есть особый вид перестановок, подобный этому: 

[2,1, 
4,5,3, 
7,8,9,10,6,
17,11,12,13,14,15,16,
18,19,20, 
29,21,22,23,24,25,26,27,28,
40,30,31,32,33,34,35,36,37,38,39,
53,41,42,43,44,45,46,47,48,49,50,51,52]

Он состоит из некоторых подперестановок (каждая строка имеет набор чисел, которые принадлежат множеству их индексов)

Мой вопрос: какое минимальное количество ходов необходимо для того, чтобы снова добраться до первой перестановки.

В качестве практической проблемы в прологе я хочу вычислить количество ходов для каждой подстановки и получить их lcm, но я не уверен, как это реализовать (как подсчитать количество ходов для каждого подсписка).-перестановка)

Любая помощь будет оценена

1 Ответ

0 голосов
/ 27 мая 2018

Перестановка p может рассматриваться как биективная функция из множества {1,2,...,n} на самого себя.Теперь то, что вы, похоже, просите, - это минимальное количество конкатенаций этой перестановки с самим собой p o p o ... o p (где o - оператор конкатенации с (f o g)(i) := f(g(i))), а вы получаете идентификационную перестановку p0 с p0(i) = i.

У вас есть перестановка, которую можно легко разложить на циклы 1->2->1, 3->4->5->3, 6->7->8->9->10->6, ... Каждый цикл требует столько же сцеплений с самим собой, сколько у него членов, чтобы получить идентичность.Поскольку у вас есть циклы длиной 2, 3, 5, 7, 3, 9, 11, 13, потребуется 2 * 9 * 5 * 7 * 11 * 13 (наименьшее общее кратное) сцеплений, пока все циклы не пройдут одновременновремя в первый раз.

...