Существует ли алгоритм реорганизации списка оптимальный по количеству перестановок?

Question

[uvelichitel]

Есть: массив или список в общем коллекция - a, b, c, d, e. Нужно получить заданный b, d, a, e, c. Буфера нет, нужно делать inplace. New(), Set(i) и Get(i) нет, да они и не нужны поскольку все равно нет буфера. Есть только Swap(i, j). Стек для учета перестановок есть. То есть их не обязательно немедленно применять, а допустимо накопить и сократить(если это возможно) перед применением.
То есть необходимо: реорганизовать массив в заданный возможно минимальным(ну или хотя бы счетным) количеством парных перестановок.
Например из "a, b, c" в "b, c, a" это -- "1-2" получаем "b, a, c" затем "2-3" получаем "b, c, a" Необходимые перестановки Swap(1, 2), Swap(2, 3).
Массив именован a, b, c, d для упрощения постановки задачи, пусть 1, 2, 3, 4, 5 в 2, 3, 1, 4, 5.
Существует ли такой алгоритм оптимальней полного перебора с доказанной корректностью?

Answer 1

[Mrrl]

Если есть операция IndexOf для поиска элемента, то оптимальное число перестановок достигается так (превращаем L1 в L2):

for(int i=0;i < L1.Count;i++){
  while(L1[i]!=L2[i]){
     L1.swap(i,L2.IndexOf(L1[i]));
  }
}

При каждом обмене текущий элемент L1[i] ставится на то место, на котором он стоял бы в списке L2, и больше с этого места не уходит.

Comments

[uvelichitel]

Алгоритм корректен и интуитивно хорош. Оптимальность доказать можете, чтоб остановить изыскания и дальше не париться?

[Mrrl]

uvelichitel: Оптимальность по числу транспозиций - могу. Достаточно проверить, что при транспозиции двух элементов число циклов в перестановке изменяется ровно на 1 (если элементы, стоящие на своём месте считать за цикл длины 1). В алгоритме, если очередной элемент L1[i] принадлежит циклу длины k, то все элементы этого цикла встанут на место за k-1 транспозицию. В итоге получается, что нужно N-M транспозиций, где M - число циклов. Это оптимальная величина.

Answer 2

[Армянское Радио]

А чем обычный qsort не угодил?

Comments

[uvelichitel]

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

[Армянское Радио]

uvelichitel: тогда нужно воспользоваться той самой теоремой о транспозициях, о которой написал brainick