Мне дается перестановка элементов {1, 2, 3, ..., N}, и мне приходится сортировать ее с помощью операции свопинга. Операция, которая меняет элементы x, y, имеет стоимость min (x, y).
Мне нужно узнать минимальную стоимость сортировки перестановки. Я жаловался на жадность, идущую от N до 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
Если поиски тривиальны, то минимальное количество свопов будет определяться количеством циклов. Он будет следовать принципу, аналогичному 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)
}
Если у вас есть перестановка чисел 1, 2,..., N, то отсортированная коллекция будет точно 1, 2,..., N. Итак, вы знаете ответ с сложность O (0) (т.е. вам вообще не нужен алгоритм).
Если вы действительно хотите отсортировать диапазон путем повторной замены, вы можете повторно "продвигать и циклировать": продвигайтесь по уже отсортированному диапазону (где a[i] == i), а затем меняйте a[i] на a[a[i]], пока не закончите цикл. Повторяйте, пока не достигнете конца. Для этого требуется не более n 1 swaps и в основном выполняет циклическое разложение перестановки.
Хм. Интересный вопрос. Быстрый алгоритм, который пришел мне на ум, - использовать элементы в качестве индексов. Сначала мы найдем индекс элемента, который имеет 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++
}
}
Использовать сортировку ведра с размером ведра 1.
Стоимость равна нулю, так как нет свопов.
Теперь сделайте проход через массив ведра и замените каждое значение обратно на соответствующую позицию в исходном массиве.
Это N свопов.
Сумма N равна N (N + 1)/2, что дает вам фиксированную стоимость.
Другая интерпретация заключается в том, что вы просто сохраняете из массива ведро, обратно в исходный массив. Это не свопы, поэтому стоимость равна нулю, что является разумным минимумом.