Сортировать числа по сумме алгоритма

Question

У меня вопрос к алгоритму, не зависящий от языка.

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

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

3 2 1 - 4
1 8 9 7 6 - 41
8 4 5 3 2 7 - 34

Хотя вы можете просто дать ответ, если хотите, если вы предпочитаете дать «подсказку» в правильном направлении (если такая возможность возможна), я бы предпочел это.

Answer 1

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

Например, 5,3,4,2,1 имеет два цикла (5,1) и (3,4,2). Цикл можно представить как начинающийся с 3, 4 находится на 3 месте, 2 на 4 месте, а 4 на 3. место. Конечная цель - 1,2,3,4,5 или (1) (2) (3) (4) (5), пять непересекающихся циклов.

Если мы переключим два элемента из разных циклов, скажем, 1 и 3, то получим: 5,1,4,2,3 и в циклической записи (1,5,3,4,2). Два цикла объединены в один цикл, это противоположно тому, что мы хотим сделать.

Если мы переключим два элемента из одного и того же цикла, скажем, 3 и 4, то получим: 5,4,3,2,1 в обозначении цикла (5,1) (2,4) (3). Один цикл делится на два меньших цикла. Это приближает нас к цели всех циклов длины 1. Обратите внимание, что любое переключение двух элементов в одном цикле разделяет цикл на два цикла.

Если мы можем определить оптимальный алгоритм для переключения одного цикла, мы можем применить его для всех циклов и получить оптимальный алгоритм для всей сортировки. Один алгоритм состоит в том, чтобы взять минимальный элемент в цикле и переключить его с тем, в чьей позиции он находится. Так что для (3,4,2) мы бы переключили 2 на 4. Это оставляет нам цикл длины 1 элемент просто переключился в правильное положение) и цикл размером на один меньше, чем раньше. Затем мы можем применить правило снова. Этот алгоритм переключает наименьшую длину цикла элемента -1 раз и каждый второй элемент один раз.

Чтобы преобразовать цикл длины n в циклы длины 1, нужно выполнить n - 1 операций. Каждый элемент должен использоваться как минимум один раз (подумайте о каждом элементе, который нужно отсортировать, его нужно переместить в правильное положение). Алгоритм, который я предложил, воздействует на каждый элемент один раз, что должны делать все алгоритмы, затем каждая другая операция выполнялась на минимальном элементе. Ни один алгоритм не может быть лучше.

Этот алгоритм использует O (n log n) для сортировки, а затем O (n), чтобы связываться с циклами. Для решения одного цикла требуется O (длина цикла), общая длина всех циклов равна n, поэтому стоимость операций цикла равна O (n). Конечное время выполнения O (n log n).

Answer 2

Я предполагаю, что память свободна, и вы можете смоделировать сортировку перед выполнением ее на реальных объектах.

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

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

Answer 3

Я сделал несколько попыток решить один из примеров вручную:

• 1 8 9 7 6
• 6 8 9 7 1 (+ 6 + 1 = 7)
• 6 8 1 7 9 (7 + 1 + 9 = 17)
• 6 8 7 1 9 (17 + 1 + 7 = 25)
• 6 1 7 8 9 (25 + 1 + 8 = 34)
• 1 6 7 8 9 (34 + 1 + 6 = 41)

Поскольку вам нужно было сместить 1, кажется, что вам, возможно, придется выполнить исчерпывающий поиск, чтобы завершить проблему - сведения о которой уже были опубликованы другим пользователем. Обратите внимание, что при использовании этого метода вы столкнетесь с проблемами, если набор данных велик.

Если проблема допускает «закрытые» ответы, вы можете просто создать жадный алгоритм, который помещает самый большой элемент в позицию - либо делая это напрямую, либо сначала поменяя самый маленький элемент в этом слоте.

Answer 4

Я думаю, что нет тривиального решения этой проблемы, и мой подход, вероятно, не лучше, чем подход с приоритетной очередью.

Найдите наименьшее число, N. Любые пары чисел, которые занимают желаемые местоположения друг друга, должны поменяться местами, кроме N. Соберите (методом грубой силы) коллекцию каждого набора чисел, которые можно взаимно поменять местами в нужных местах, так, чтобы стоимость сортировки множества между собой была меньше стоимости замены каждого элемента множества на N. Эти наборы будут состоять из нескольких циклов. Поменяйте местами в этих циклах таким образом, чтобы наименьшее число менялось местами дважды. Поменяйте местами все оставшиеся числа, составляющие цикл, включая N, используя N в качестве заполнителя.

Answer 5

Сравнения и обходы, очевидно, приходят бесплатно, вы можете предварительно рассчитать «расстояние», которое должно пройти число (и, фактически, окончательный порядок сортировки). Загадка - это алгоритм обмена.

Минимизация общих свопов, очевидно, важна. Минимизация свопов с большими числами также важна.

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

Answer 6

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

Answer 7

Как подсказка, это пахнет динамическим программированием; это может быть недостаточно точный намек, чтобы помочь, но я бы предпочел начать с слишком малого!