uvelichitel
@uvelichitel
habrahabr.ru/users/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.
Существует ли такой алгоритм оптимальней полного перебора с доказанной корректностью?
  • Вопрос задан
  • 2366 просмотров
Решения вопроса 1
Mrrl
@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, и больше с этого места не уходит.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
gbg
@gbg Куратор тега Программирование
Любые ответы на любые вопросы
А чем обычный qsort не угодил?
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы