Как найти кратчайшую последовательность перестановок между двумя разными перестановками?

Question

Я ищу какой-то алгоритм, который помог бы мне решить задачу, стоящую передо мной. Мне нужно найти метод, чтобы найти (НЕ только считать) все перестановки (обмен двух элементов) в данной перестановке, которая требуется для преобразования ее в другую данную перестановку. Было бы здорово, если бы метод мог найти минимальное количество перестановок, ведущих от одной перестановки к другой. Кто-нибудь может дать мне совет или полное решение этой проблемы?

Answer 1

Сначала определите, куда должно идти каждое значение. Затем вы найдете циклы ходов. Возьмем, к примеру, эти данные:

source: [5, 3, 0, 7, 1, 6, 4, 8]
target: [3, 1, 0, 4, 5, 7, 8, 6]
(index:  0  1  2  3  4  5  6  7  ) 

Затем мы можем получить, что значение по индексу 0 (то есть 5) должно идти к индексу 4, а одно по индексу 4 должно идти по индексу 1, а другоепо индексу 1 следует перейти к индексу 0, завершив этот цикл. Итак, мы находим эти циклы:

0 -> 4 -> 1 (and back to start)
2
3 -> 5 -> 7 -> 6 (and back to start) 

Итак, у нас есть три цикла. Обратите внимание, что значение в индексе 2 уже имеет свой правильный индекс, и поэтому оно находится в собственном цикле.

Первый цикл может быть выполнен с помощью следующих перестановок, начиная с последней пары и возвращаясь назад. :

index 4 <-> index 1
index 0 <-> index 4 

Не требуется подкачка для значения с индексом 2.

Третий цикл может быть выполнен со следующими перестановками:

index 7 <-> index 6
index 5 <-> index 7
index 3 <-> index 5 

Числосвопы к выполнить цикл равен его длине минус 1.

Таким образом, в приведенном выше примере количество свопов составляет (3-1) + (1-1) + (4-1) = 2 + 0 + 3 = 5.