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

Question

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

例如:

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

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

3 -> 1

也就是说，因为索引 3 处的元素被移动到索引 1。请注意 B 和 C 确实更改了索引，但这只是因为当 D 在索引 1 处插入时它们正在为 D “腾出空间”，所以这步骤不应包含在移动列表中!

另一个例子:

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在列表中并仅更改该子序列之外的元素的位置。