如何比较两条路径

Question

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

A, B, C, D

可能的配置可能是：A, B, D, C 或 D, C, A, B。

我需要两个比较两条路径以找出这两条路径之间的差异，这样该过程的输出 returns 将第二条路径转换为第一条路径所需的一组交换操作一.

例如，给定以下路径：

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] 是 Y 中 X[i] 城市的索引。然后你只计算 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)。所以你以相反的顺序交换循环元素。

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

如何比较两条路径

How to compare two paths

algorithm

swap

set

data-structures