Самый быстрый способ перевернуть список? (Только смежные элементы могут поменяться местами)

Question

Это теоретический / математический вопрос.Может быть, кто-то найдет для этого применение.

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

Самый простой способ - что-то похожее на пузырьковую сортировку:

a, b, c, d, e, f -> b, a, c, d, e, f -> b, c, a, d, e, f -> b, c, d, a, e, f -> ... -> f, e, d, c, b, a

Но есть ли более быстрый способ?

Answer 1

Нет, я думаю, что у вас меньше всего свопов. У вас есть , чтобы выполнить пять, чтобы получить a до конца, затем еще четыре, чтобы получить b до второй от последней позиции и т. Д.

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

Следовательно, минимальный счет свопа для {a, b, c, d, e, f} равен 5 + 4 + 3 + 2 + 1. Это примерно так же эффективно, как пузырьковая сортировка, поэтому, вероятно, ее следует избегать для любых приличных данных. Однако даже пузырьковая сортировка в порядке, если размеры данных достаточно малы, чтобы никто не заметил.

Мне кажется, что если вашим доменом является Inkscape, на самом деле не будет особенно огромного числа слоев. Для более общего домена, вы должны сосать его и видеть: -)

Answer 2

Самый быстрый способ - пройти по тому же списку от последнего элемента к первому. Нет обменов вообще.