Сортировка чисел по алгоритму суммирования

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

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

Answer 4

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

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

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

Answer 5

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

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

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

Answer 6

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

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

Answer 7

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

• 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, вам, возможно, придется выполнить исчерпывающий поиск, чтобы решить проблему, подробности которой уже были отправлены другим пользователем. Обратите внимание, что при выполнении этого метода вы столкнетесь с проблемами, если набор данных является большим.

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