Сортировка перестановки с минимальной стоимостью

Ответ 1

Будет ли это оптимальным:

Find element 2
If it is not at correct place already

    Find element at position 2
    If swapping that with 2 puts both to right place

        Swap them
        Cost = Cost + min(2, other swapped element)

repeat

   Find element 1
   If element 1 is at position 1

      Find first element that is in wrong place
      If no element found

          set sorted true

      else

         Swap found element with element 1
         Cost = Cost + 1

   else

      Find element that should go to the position where 1 is
      Swap found element with element 1
      Cost = Cost + 1

until sorted is true

Ответ 2

Если поиски тривиальны, то минимальное количество свопов будет определяться количеством циклов. Он будет следовать принципу, аналогичному Cuckoo Hashing. Вы берете первое значение в перестановке и смотрите значение в индексе значения в исходном индексе. Если они совпадают, замените их на одну операцию.

[ 3 2 1]: значение 3 относится к индексу один, поэтому посмотрите на значение в индексе 3.
[3 2 1]: значение 1 находится в индексе 3, поэтому существует два цикла индекса. Поменяйте эти значения.

Если нет, нажмите первый индекс на стек и найдите индекс для значения второго индекса. В итоге будет цикл. В этот момент начните замену, выбирая значения из стека. Это займет несколько свопов, равных n-1, где n - длина цикла.

[ 3 1 2]: значение 3 относится к индексу один, поэтому посмотрите на значение в индексе 3.
[3 1 2]: значение 2 находится в индексе 3, поэтому добавьте 3 в стек и найдите индекс 2. Также сохраните 3 как начальное значение цикла.
[3 1 2]: значение 1 находится в индексе 2, поэтому добавьте 2 в стек и попробуйте индексировать 1.
[ 3 1 2]: значение 3 - начало цикла, поэтому swap pop 2 укладывается в стек и меняет значения 1 и 2.
[1 3 2]: поп 3 со стека и свопинг 2 и 3, в результате получается отсортированный список с 2 свопами.

[1 2 3]

При таком алгоритме максимальное число свопов будет N-1, где N - общее количество значений. Это происходит, когда существует цикл N длины.

EDIT: Этот алгоритм дает минимальное количество свопов, но не обязательно минимальное значение, используя функцию min (x, y). Я не сделал математику, но считаю, что единственное время, когда swap (x, y) = {swap (1, x), swap (1, y), swap (1, x)} не следует использовать когда x в {2,3} и n < 2; Должно быть достаточно легко написать это как особый случай. Может быть, лучше проверить и поместить 2 и 3 явно, затем следовать алгоритму, упомянутому в комментариях, для достижения сортировки в двух операциях.

РЕДАКТИРОВАТЬ 2: Довольно уверен, что это поймает все случаи.

while ( unsorted ) {
    while ( 1 != index(1) )
        swap (1 , index (1) )

    if (index(2) == [email protected](2))
        swap (2, [email protected](2) )

    else
        swap (1 , highest value out of place)
}

Ответ 3

Если у вас есть перестановка чисел 1, 2,..., N, то отсортированная коллекция будет точно 1, 2,..., N. Итак, вы знаете ответ с сложность O (0) (т.е. вам вообще не нужен алгоритм).

Если вы действительно хотите отсортировать диапазон путем повторной замены, вы можете повторно "продвигать и циклировать": продвигайтесь по уже отсортированному диапазону (где a[i] == i), а затем меняйте a[i] на a[a[i]], пока не закончите цикл. Повторяйте, пока не достигнете конца. Для этого требуется не более n   1 swaps и в основном выполняет циклическое разложение перестановки.

Ответ 4

Хм. Интересный вопрос. Быстрый алгоритм, который пришел мне на ум, - использовать элементы в качестве индексов. Сначала мы найдем индекс элемента, который имеет 1 в качестве значения, и замените его на элемент этого числа. В конце концов, это закончится тем, что 1 появится в первой позиции, это означает, что вам нужно поменять номер 1 с каким-то элементом, который еще не находится в позиции, и продолжить. Это вершина на 2 * N-2 и имеет нижний предел для N-1 для перестановки (2,3,..., N, 1), но точная стоимость будет отличаться.

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

set sorted=false
while (!sorted) {
    if (element 1 is in place) {
        if (element 2 is in place) {
            find any element NOT in place
            if (no element found) sorted=true 
            else {
                swap 1 with element found
                cost++
            }
        } else {
            swap 2 with element at second place
            cost+=2
        }
    } else {
        find element with number equals to position of element 1
        swap 1 with element found
        cost++
    }
}

Ответ 5

Использовать сортировку ведра с размером ведра 1.
Стоимость равна нулю, так как нет свопов. Теперь сделайте проход через массив ведра и замените каждое значение обратно на соответствующую позицию в исходном массиве.
Это N свопов.
Сумма N равна N (N + 1)/2, что дает вам фиксированную стоимость.

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