如何比較兩條路徑

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是置換的長度。