产生相同结果

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”解更具数学性质。