如何比较两条路径

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]城市的指数。然后，您只需计算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是置换的长度。