arrays - 数组变异算法

Question

我正在寻找以下问题的解决方案:

给定一个数组“a”和一个数组“b”，找到一组操作，当应用于“a”时，将“a”转换为“b”。

例如，假设我有:

a = [1,2,3]
b = [3,2,4]
c = transmute(a, b)

我现在希望 c 包含如下内容:

[["remove", 0], ["add", 2, 4], ["swap", 0, 1]]

按照给定的顺序在“a”上添加这些操作应该产生“b”:

[1,2,3] => [2,3] => [2,3,4] => [3,2,4]

这是一个非常简单的 Ruby 实现:https://gist.github.com/4455256 .这个假设数组中没有重复项(这不是一个好的假设)。我认为它也是 O(n²)，如果有更高性能的东西就好了。

有没有已知的算法可以做到这一点？我可以做任何进一步的阅读吗？您对如何改进有什么建议吗？

Answer 1

您可以分阶段进行来解决这个问题。按照我的想法，应该有3个阶段。一个 O(N) 的解决方案是可能的。

将数组A复制到数组C，将数组B复制到数组D。

1. 现在，比较 2 个数组 C 和 D。删除 C 中不存在于 D 中的元素。这些是需要从数组 A 中删除的元素。如果我们在这一步使用 HashMap，那么它可以在 O(N) 内完成
2. 再次比较 C 和 D，删除 D 中不在 C 中的元素。这些元素本质上就是我们将添加到数组 A 中的元素。
3. 因此，现在我们有 2 个数组 - C 和 D，它们基本上具有相同的元素。我们只需要了解如何交换这些元素以使它们看起来相似。
4. 一旦它们看起来相似，我们就可以将 A 中缺少的元素添加到 D 中。将您在步骤 2 中删除的元素添加回数组 D。通过与原始数组 A 的比较，它们可以按正确的顺序添加。

因为，步骤 1、2、4 非常简单。我将解释如何确定交换顺序。让我们举个例子。如果当前我们的数组 C 看起来像 1,3,2 而 D 看起来像 3,2,1。我们将 D 中每个索引处的值与 C 中的相应值进行比较。如果它们不同，则我们标记一条从 C 中的元素到 D 中的元素的有向边。因此，在索引 0 处，C 有 1，D 有 3。它们不同，因此我们绘制一条从 1 到 3 的有向边。1->3。类似地，我们为索引 1 绘制一条从 3 到 2 的边。索引 2 从 2 到 1 的边。

这将我们引向一个DAG。你可以尝试各种东西，比如 DFS，看看，我会在这里说明结果。没有。交换的数量将是(图中的节点数 - 1)。 图形的 DFS 遍历将告诉交换发生的顺序。

注意:如果数组中有重复的元素，则需要更多的簿记，但同样的解决方案仍然有效。

如果您无法通过 DAG 交换算法的阶段。请看@handcraftsman 引用的问题，即string transposition algorithm .它针对同一问题提出了类似的方法。