识别产生相同结果的交换序列
我有一个关联数组，我在其中存储键值对，可以在其中执行交换操作：
swap(a, b) // a <-> b
{
temp = map.value(b);
map.value(b) = map.value(a);
map.value(a) = temp;
}
现在，给定一系列交换，我想知道我执行的下一次交换是否会导致关联数组进入某种状态之前在：
例如序列：
1 <-> 2
2 <-> 1
并且
1 <-> 2
2 <-> 3
3 <-> 1
2 <-> 3
两者都不执行任何操作。
我希望能够通过查看交换序列本身来检测这一点。我猜测此类问题有一个数学公式，但我似乎无法弄清楚。
我观察到第一个示例是一个循环，第二个示例有一个循环，因此“检测有向图中的循环”可能是解决方案的一部分，但我不确定这将如何适合我正在寻找的算法。
该算法还应该适用于交错的不相关交换，最简单的例子是：
1 <-> 2
100 <-> 200
2 <-> 1
200 <-> 100
I have an associative array where I store key-value pairs, on which I can perform swap operations:
swap(a, b) // a <-> b
{
temp = map.value(b);
map.value(b) = map.value(a);
map.value(a) = temp;
}
Now, given a sequence of swaps, I would like to know if the next swap I perform causes the associative array to go into a state it was previously in:
e.g. the sequences:
1 <-> 2
2 <-> 1
and
1 <-> 2
2 <-> 3
3 <-> 1
2 <-> 3
both do nothing.
I want to be able to detect this by looking at the swap sequence itself. I'm guessing there is a mathematical formulation of problems of this kind, but I cannot seem to figure it out.
I observe that the first example is a loop and the second has a loop, so "detecting loops in a directed graph" might be part of the solution, but I'm not sure how this will fit into the algorithm I am looking for.
The algorithm should also work for unrelated swaps which are interleaved, the simplest example of this being:
1 <-> 2
100 <-> 200
2 <-> 1
200 <-> 100
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这是排列的应用（并不是真正的图论应用）。
由于这些是键值对，大概它们可能是稀疏的数字集，如上一个示例 (1, 2, 100, 200)，甚至是字符串：
以及数字，我会做以下操作（有至少有两种方法可以做到这一点）：
然后：
A.程序解决方案：
2A。在 ML 映射本身上按顺序执行交换。
3A。要检查排列是否使映射完好无损，请验证 ML[L[i]] = i 对于 0 到 N-1 之间的每个整数 i，其中 N = L 的长度。
B. 矩阵解决方案：
将每个交换表示为排列矩阵，使用列表 L 和映射 ML 从交换键转换 ->整数索引。例如，舞者<-> Vixen 交换元素 0 和 1，用置换矩阵表示：
) 并将置换矩阵相乘。然后检查最后是否有单位矩阵。
“A”解决方案更有效，但带有矩阵的“B”解决方案本质上更数学化。
This is an application of permutations (and not really an application of graph theory).
Since these are key-value pairs, where presumably they could be sparse sets of numbers like your last example (1, 2, 100, 200), or even strings:
as well as numbers, what I would do is the following (there are at least two ways to do this):
Then either:
A. Procedural solution:
2A. Perform the swaps, in order, on the ML map itself.
3A. To check if the permutation leaves the map intact, verify that ML[L[i]] = i for each integer i between 0 and N-1 where N = the length of L.
B. Matrix solution:
Represent each swap as a permutation matrix, using the list L and map ML to convert from swap keys -> integer indexes. For example, Dancer <-> Vixen swaps elements 0 and 1, which is represented by the permutation matrix:
) and multiply the permutation matrices. Then check if you have the identity matrix at the end.
The "A" solution is more efficient but the "B" solution with matrices is more mathematical in nature.