Как уменьшить количество операций перемещения в массиве?

Question

скажем, у меня есть массив чисел, например, [0, 1, 2, 3, 4, 5] и я хочу получить массив, например [2, 1, 4, 0, 5, 3]. В моем распоряжении есть один метод, который я могу использовать:

move(fromIndex, toIndex)

Таким образом, чтобы получить желаемый массив, я мог вызывать метод несколько раз:

move(2, 0); // [2, 0, 1, 3, 4, 5]
move(1, 2); // [2, 1, 0, 3, 4, 5] (swapped 2 with 0)

move(4, 2); // [2, 1, 4, 0, 3, 5]
move(3, 4); // [2, 1, 4, 3, 0, 5] (swapped 4 with 0)

move(4, 3); // [2, 1, 4, 0, 3, 5] (swapped 0 with 3)

move(5, 4); // [2, 1, 4, 0, 5, 3] (swapped 5 with 3)

Таким образом, у меня также есть список move() операций для достижения желаемого результата. Список операций move() может быть уменьшен в размере путем изменения порядка и индексов, чтобы в итоге получить тот же результат.

Есть ли алгоритм, который я могу использовать в своем списке move() операций, чтобы сократить количество операций до минимума?

Answer 1

Мы можем создать график с элементом, указывающим на число, с которым его нужно поменять местами, чтобы добраться до желаемой позиции.Следовательно, мы получим несколько графов с возможными циклами.В вашем конкретном случае мы получим

2-> 0-> 3-> 5-> 4-> 2 (первый и последний элементы обозначают цикл)

Это означаетчто 2 хочет поменяться местами с 0, чтобы добраться до желаемой позиции.Точно так же 0 хочет поменяться местами с 3, чтобы добраться до желаемой позиции.Обратите внимание, что 1 не хочет меняться местами.

Теперь мы можем поменять местами два смежных элемента графа, чтобы уменьшить размер графа на 1. Скажем, мы поменяли местами 3 и 5, теперь arr = [0,1,2,5,4,3].Теперь 3 находится в желаемом состоянии, поэтому мы можем удалить его из графика

2-> 0-> 5-> 4-> 2

Нам нужно повторить этот процесс(м-1) раз, чтобы полностью удалить график.Здесь m представляет количество ребер графа.Мы можем иметь несколько несвязных графов или графов без циклов.Нам нужно убедиться, что мы меняем элементы одного и того же графа.Окончательный ответ будет суммой всех шагов (т. Е. M-1 для каждого компонента) графика.