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

Question

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

Например:

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

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

3 -> 1 

То есть, потому что элемент с индексом 3 был перемещен в индекс 1. Заметим, что В и С меняются индексы, но это только потому, что они " делая пространство "для 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

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

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']