algorithm - 如何比较两条路径

Question

我的数据结构是由城市列表表示的路径。例如，如果城市是

A, B, C, D

可能的配置可能是:A, B, D, C或 D, C, A, B .

我需要两个比较两条路径，以便找到这两条路径之间的差异，以便此过程的输出返回将第二条路径转换为第一条路径所需的一组交换操作。

例如，给定以下路径:

X = {A, B, D, C}
Y = {D, C, A, B}
indexes = {0, 1, 2, 3}

一种可能的路径转换方式 Y进入X将是以下交换的集合:{0-2, 1-3} .

{D, C, A, B} --> [0-2] --> {A, C, D, B} --> [1-3] --> {A, B, D, C}

是否有任何已知(且快速)的算法可以计算此集合？

Answer 1

您的问题看起来像是计算将一种排列转换为另一种排列的最少交换次数的问题。

事实上这是一个众所周知的问题。关键思想是创建新的排列 P，使得 P[i] 是 中 X[i] 城市的索引Y。然后，您只需计算 P 中的 C 循环总数。答案是 len(X) - C，其中 len(X) 是 X 的大小。

在您的例子中，P 看起来像:3, 4, 1, 2。它有两个循环:3, 1 和 4, 2。所以答案是 4 - 2 = 2。

总复杂度是线性的。

有关详细信息，请参阅 this answer .它更详细地解释了该算法。

编辑

好的，但我们如何才能获得交换，而不仅仅是他们的数量？请注意，在此解决方案中，如果循环的长度为 N，我们会独立地对每个循环进行 N - 1 交换。所以，如果你有循环 v(0), v(1), ..., v(N - 1), v(N) 你只需要交换 v(N) , v(N - 1), v(N - 1), v(N - 2), ..., v(1), v(0)。所以你以相反的顺序交换循环元素。

此外，如果您有长度为 L(1), L(2), ..., L(C) 的 C 循环，交换次数为 L(1) - 1 + L(2) - 1 + ... + L(C) - 1 = L(1) + L(2) + ... + L(C) - C = LEN - C 其中 LEN 是排列的长度。