產生相同結果

Question

我有一個關聯數組，其中我存儲鍵值對，其上我可以執行交換操作識別交換序列：

swap(a, b) // a <-> b 
    { 
    temp = map.value(b); 
    map.value(b) = map.value(a); 
    map.value(a) = temp; 
    } 

現在，給定的交換的序列，我想要知道我執行的下一個交換是否導致關聯陣列進入之前的狀態：

eg序列：

1 <-> 2 
2 <-> 1 

和

1 <-> 2 
2 <-> 3 
3 <-> 1 
2 <-> 3 

都無能爲力。

我希望能夠通過查看交換序列本身來檢測到這一點。我猜測有這樣的問題的數學表述，但我似乎無法弄清楚。

我觀察到的第一個例子是一個環和第二已經一個循環，所以「有向圖中檢測環路」可能是解決方案的一部分，但我不知道這將如何適應進入我正在尋找的算法。

該算法還應該交插無關互換工作，這是最簡單的例子：

1 <-> 2 
100 <-> 200 
2 <-> 1 
200 <-> 100 

Answer 1

這是一個應用程序permutations（而不是真正的圖論的應用程序）。

由於這些鍵值對，其中想必他們可能是稀疏組數字像你的最後一個例子（1，2，100，200），甚至字符串：

Dancer <-> Vixen 
Prancer <-> Blitzen 
Comet <-> Donner 
Vixen <-> Rudolph 
Prancer <-> Dasher 
Comet <-> Cupid 
Vixen <-> Dasher 
Cupid <-> Donner 
Vixen <-> Blitzen 
Prancer <-> Dasher 
Dancer <-> Rudolph 
Prancer <-> Rudolph 
Comet <-> Cupid 
Prancer <-> Vixen 

以及數，我會做的是以下（至少有兩種方法可以做到這一點）：

1. 掃描序列以獲得交換密鑰的列表L和映射ML，使得L [ML [k] ] = k。在上面的例子中，L = [Dancer，Vixen，Prancer，Blitzen，Comet，Donner，Rudolph，Dasher，Cupid]和ML = {Dancer：0，Vixen：1，Prancer：2，Blitzen：3，Comet：唐納：5，魯道夫：6，Dasher的：7，丘比特：8}

然後：

A.程序溶液：

2A。依次在ML地圖上執行交換。 3A。爲了檢查置換是否完整保留映射，驗證對於0到N-1之間的每個整數i，其中N = L的長度，ML [L [i]] = i。

B.矩陣求解：

將每個交換表示爲置換矩陣，使用列表L和映射ML從交換鍵 - >整數索引進行轉換。例如，舞者< - >潑婦互換元素0和1，這是由置換矩陣表示：

010000000 
100000000 
001000000 
000100000 
000010000 
000001000 
000000100 
000000010 
000000001 

）和乘以置換矩陣。然後檢查最後是否有身份矩陣。

---

「A」解決方案更高效，但帶矩陣的「B」解更具數學性質。