如何找到重新排序列表以获取另一个列表所需的步骤列表？

Question

假设我们必须列出（表示为数组或任何语言的任何内容）。这些列表同样长并且包含相同的唯一元素 - 但顺序不同。

例如：

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

现在我要查找的是重新排序第一个列表以匹配第二个列表所需的步骤列表。在这个例子中，只有一个步骤：

3 -> 1

也就是说，因为索引 3 处的元素已移动到索引 1。请注意，B 和 C 确实更改了索引，但这只是因为当 D 在索引 1 处插入时它们是 "making space" , 因此这一步不应包含在移动列表中！

另一个例子：

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 而不是执行第一次移动后的索引。

这些步骤都是"performed at once" - 这意味着没有顺序，但我们只是通过将移动的元素放在它们应该在的位置然后用剩余的元素填充剩余的槽来创建一个新列表。

现在我的问题是：有人知道执行此操作的算法吗？

提前致谢！ :)

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

如何找到重新排序列表以获取另一个列表所需的步骤列表？

How to find a list of steps needed to reorder a list to get another list?

arrays

algorithm

list

reorderlist