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

Question

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

Например:

First list: A, B, C, D
Second list: A, D, B, C

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

3 -> 1

То есть, потому что элемент в индексе 3 был перемещен в индекс 1. Обратите внимание, что B и C изменяют индексы, но это только потому, что они "освобождают место" для D, когда он вставляется в индекс 1, поэтому этот шаг не должен быть включенным в список ходов!

Другой пример:

First list: A, B, C, D, E, F
Second list: D, B, A, C, E, F
Changes:  3 -> 0, 1 -> 1

Поскольку D был перемещен в индекс 0, а B был перемещен в 1. Обратите внимание, что для B мы используем исходный индекс 1 вместо того, что было бы после первого перемещения.

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

Теперь мой вопрос: кто-нибудь знает какой-либо алгоритм для этого?

Заранее спасибо!:)

Answer 1

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

Answer 2

Если вам не нужен кратчайший список шагов и тривиальное решение по какой-то причине неприемлемо, то вот мое решение на python. Я думаю, что это достаточно просто понять:

first = ['A', 'B', 'C', 'D']
second = ['A', 'D', 'B', 'C']
steps = []
tmp = second[:]  # copy second list to temp list
for pos in range(len(first)):
    # find position where first and temp lists are different
    if first[pos] != tmp[pos]:
        # get element that should be placed in position 'pos'
        element = first[pos]
        # get position of that element in second list
        sec_pos = second.index(element)
        # add step: move element from sec_pos to pos
        step = '%d -> %d' % (sec_pos, pos)
        steps.append(step)
        # do permutation in temp list
        tmp.remove(element)  # remove element
        tmp.insert(pos, element)  # put it in proper position
        # print step and intermediate result
        print step, tmp
print steps

Выход:

2 -> 1 ['A', 'B', 'D', 'C']

3 -> 2 ['A', 'B', 'C', 'D']

['2 -> 1', '3 -> 2']