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 。然后你只需计算总周期数 C在 P 。答案是len(X) - C ，其中len(X)大小为X .

就您而言P看起来像:3, 4, 1, 2 。它有两个周期:3, 1和4, 2 。所以答案是4 - 2 = 2 .

总复杂度是线性的。

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

编辑

好吧，但是我们如何才能获得掉期，而不仅仅是它们的数量呢？请注意，在此解决方案中，我们独立地对每个周期重新排序 N - 1如果循环长度为 N 则交换。所以，如果你有周期 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是排列的长度。