查找同构排列集的算法
Algorithm to find isomorphic set of permutations
我有一组排列，我想删除同构排列。
We have S sets of permutations, where each set contain K permutations, and each permutation is represented as and array of N elements. I'm currently saving it as an array int pset[S][K][N], where S, K and N are fixed, and N is larger than K.
Two sets of permutations, A and B, are isomorphic, if there exists a permutation P, that converts elements from A to B (for example, if a is an element of set A, then P(a) is an element of set B). In this case we can say that P makes A and B isomorphic.
我目前的算法是：
- 我们选择所有对
s1 = pset[i] 和 s2 = pset[j]，这样 i < j
- 选择集（
s1 和 s2）中的每个元素的编号从 1 到 K。这意味着每个元素都可以表示为 s1[i] 或 s2[i]，其中 0 < i < K+1
- 对于
K 元素的每个排列 T，我们执行以下操作：
- 找到排列
R，使得 R(s1[1]) = s2[1]
- 检查
R是否是使s1和T(s2)同构的排列，其中T(s2)是集合[=的元素（排列）的重新排列33=]，所以基本上我们只检查是否 R(s1[i]) = s2[T[i]]，其中 0 < i < K+1
- 如果不是，那么我们进入下一个排列
T。
此算法运行速度非常慢：O(S^2) 第一步，O(K!) 遍历每个排列 T，O(N^2) 找到 R , 和 O(K*N) 检查 R 是否是使 s1 和 s2 同构的排列 - 所以它是 O(S^2 * K! * N^2).
Question: Can we make it faster?
在A中取a0。然后求其逆（快，O(N)），称其为a0inv。然后在 B 中选择一些 i 并定义 P_i = b_i * ainv 并检查 P_i * a 在 A 上变化 a 时是否生成 B。对 B 中的每个 i 执行此操作。如果您没有找到关系成立的任何 i，则这些集合不是同构的。如果找到这样的 i，则这些集合是同构的。它检查的每对集合的运行时间是 O(K^2)，你需要检查 O(S^2) 个集合，所以你最终得到 O(S^2 * K^2 * N).
PS：我在这里假设“将A映射到B”你的意思是在排列组合下进行映射，所以P(a)实际上是排列P 由排列 a 组成，我已经使用了这样一个事实，即如果 P 是一个排列，那么必须存在一个 i 对于 Pa = b_i一些 a.
编辑 我决定取消删除我的答案，因为我不相信基于搜索的前一个 (@Jean Logeart) 是正确的。如果是，我会很乐意删除我的，因为它表现更差，但我想我有一个反例，请参阅 Jean 的回答下面的评论。
您可以排序比较：
// 1 - sort each set of permutation
for i = 0 to S-1
sort(pset[i])
// 2 - sort the array of permutations itself
sort(pset)
// 3 - compare
for i = 1 to S-1 {
if(areEqual(pset[i], pset[i-1]))
// pset[i] and pset[i-1] are isomorphic
}
一个具体的例子：
0: [[1,2,3],[3,2,1]]
1: [[2,3,1],[1,3,2]]
2: [[1,2,3],[2,3,1]]
3: [[3,2,1],[1,2,3]]
1 之后：
0: [[1,2,3],[3,2,1]]
1: [[1,3,2],[2,3,1]] // order changed
2: [[1,2,3],[2,3,1]]
3: [[1,2,3],[3,2,1]] // order changed
2 之后：
2: [[1,2,3],[2,3,1]]
0: [[1,2,3],[3,2,1]]
3: [[1,2,3],[3,2,1]]
1: [[1,3,2],[2,3,1]]
3 之后：
(2, 0) not isomorphic
(0, 3) isomorphic
(3, 1) not isomorphic
复杂度如何？
- 1 是
O(S * (K * N) * log(K * N))
- 2 是
O(S * K * N * log(S * K * N))
- 3 是
O(S * K * N)
所以整体复杂度是O(S * K * N log(S * K * N))
假设s1,s2\in S的两个元素是同构的。那么如果 p1 和 p2 是排列，那么 s1 同构于 s2 iff p1(s1) 同构于 p2(s2) 其中 pi(si) 是通过将 pi 应用于 si 中的每个元素而获得的排列集。
对于 1...s 中的每个 i 和 1...k 中的每个 j，选择 si 的第 j 个成员，并找到将其变为统一的排列。将其应用于 si 的所有元素。将每个 k 排列散列为一个数字，获得 k 个数字，对于 i 和j，成本 nk。
比较 i 和 j 两个不同值的散列集是 k^2 < nk。因此，您可以找到成本为 s^2 k^3 n 的候选匹配集。如果实际匹配数很少，则整体复杂性远低于您在问题中指定的值。
要检查两个集合 S₁ 和 S₂ 是否同构，您可以进行更短的搜索。
如果它们是同构的，则有一个排列 t 将 S₁ 的每个元素映射到 的一个元素S2；要找到 t 你可以选择 S₁ 的任何固定元素 p 并考虑排列
t₁ = (1/p) q₁
t₂ = (1/p) q₂
t₃ = (1/p) q₃
...
对于 S2 的所有元素 q。因为，如果存在有效的 t，则它必须将元素 p 映射到 S₂ 的元素，所以只有映射 p 到 S2 的元素的排列是可能的候选者。
此外，给定一个候选人 t 来检查两组排列是否 S₁t 和 S₂相等时，您可以使用计算出的散列作为每个元素的散列码的 x 或，仅当散列匹配时才对所有排列进行全面检查。
对此有一个非常简单的解决方案：换位。
如果两个集合同构，则表示存在one-to-one映射，集合S1中索引i处所有数字的集合等于所有数字的集合在集合 S2 中的某个索引 k 处。我的推测是没有两个non-isomorphic集有这个属性.
(1) Jean Logeart 的例子：
0: [[1,2,3],[3,2,1]]
1: [[2,3,1],[1,3,2]]
2: [[1,2,3],[2,3,1]]
3: [[3,2,1],[1,2,3]]
Perform ONE pass:
Transpose, O(n):
0: [[1,3],[2,2],[3,1]]
Sort both in and between groups, O(something log something):
0: [[1,3],[1,3],[2,2]]
Hash:
"131322" -> 0
...
"121233" -> 1
"121323" -> 2
"131322" -> already hashed.
0 and 3 are isomorphic.
(2) vsoftco 的 counter-example 在他对 Jean Logeart 的回答的评论中：
A = [ [0, 1, 2], [2, 0, 1] ]
B = [ [1, 0, 2], [0, 2, 1] ]
"010212" -> A
"010212" -> already hashed.
A and B are isomorphic.
您可以将每个集合变成 transposed-sorted 字符串或散列或任何压缩对象以进行 linear-time 比较。请注意，此算法将所有三个集合 A、B 和 C 视为同构，即使一个 p 将 A 转换为 B 而另一个 p 将 A 转换为 C。显然，在这种情况下，有 p 可以将这三个集合中的任何一个转换为另一个集合，因为我们所做的只是将一个集合中的每个 i 移动到特定的 k在另一个。如果像您所说的那样，您的目标是 "remove isomorphic permutations," 您仍然会得到要删除的集合列表。
解释：
假设在排序后的哈希中，我们记录了每个 i 来自哪个排列。 vsoftco 的 counter-example:
010212 // hash for A and B
100110 // origin permutation, set A
100110 // origin permutation, set B
为了确认同构，我们需要证明 i 在第一组的每个索引中分组移动到第二组中的 一些 索引，哪个索引无关紧要。对 i 的组进行排序不会使解决方案无效，而是用于确认集合之间的 movement/permutation。
现在根据定义，哈希 中的每个数字和哈希 中每个组中的每个数字在原始排列中对每个集合恰好表示一次。然而，我们选择在散列中排列每组 i 中的数字，我们保证该组中的每个数字代表集合中的不同排列；在我们理论上分配该数字的那一刻，我们保证它是 "reserved" 仅用于该排列和索引。对于给定的数字，比如2，在两个哈希中，我们保证它来自集合A中的一个索引和排列，而在第二个哈希中对应于集合[中的一个索引和排列=19=]。这就是我们真正需要展示的全部 - 一组（一组不同的 i's）中每个排列的一个索引中的数字仅在 一个索引 中另一组（一组不同的k）。数字属于哪个排列和索引是无关紧要的。
请记住，任何与集合 S1 同构的集合 S2 都可以使用一个置换函数或应用于 [=15= 的不同置换函数的各种组合从 S1 导出]的成员。我们的数字和组的排序或重新排序实际上代表的是我们选择分配作为同构解决方案的排列，而不是实际分配哪个数字来自哪个索引和排列。这里又是 vsoftco 的 counter-example，这次我们将添加哈希的原始索引：
110022 // origin index set A
001122 // origin index set B
因此我们的permutation同构的解是：
或者，按顺序：
（请注意，在 Jean Logeart 的示例中，同构的解决方案不止一种。）
我有一组排列，我想删除同构排列。
We have
Ssets of permutations, where each set containKpermutations, and each permutation is represented as and array ofNelements. I'm currently saving it as an arrayint pset[S][K][N], whereS,KandNare fixed, and N is larger than K.Two sets of permutations,
AandB, are isomorphic, if there exists a permutationP, that converts elements fromAtoB(for example, ifais an element of setA, thenP(a)is an element of setB). In this case we can say thatPmakesAandBisomorphic.
我目前的算法是：
- 我们选择所有对
s1 = pset[i]和s2 = pset[j]，这样i < j - 选择集（
s1和s2）中的每个元素的编号从1到K。这意味着每个元素都可以表示为s1[i]或s2[i]，其中0 < i < K+1 - 对于
K元素的每个排列T，我们执行以下操作：- 找到排列
R，使得R(s1[1]) = s2[1] - 检查
R是否是使s1和T(s2)同构的排列，其中T(s2)是集合[=的元素（排列）的重新排列33=]，所以基本上我们只检查是否R(s1[i]) = s2[T[i]]，其中0 < i < K+1 - 如果不是，那么我们进入下一个排列
T。
- 找到排列
此算法运行速度非常慢：O(S^2) 第一步，O(K!) 遍历每个排列 T，O(N^2) 找到 R , 和 O(K*N) 检查 R 是否是使 s1 和 s2 同构的排列 - 所以它是 O(S^2 * K! * N^2).
Question: Can we make it faster?
在A中取a0。然后求其逆（快，O(N)），称其为a0inv。然后在 B 中选择一些 i 并定义 P_i = b_i * ainv 并检查 P_i * a 在 A 上变化 a 时是否生成 B。对 B 中的每个 i 执行此操作。如果您没有找到关系成立的任何 i，则这些集合不是同构的。如果找到这样的 i，则这些集合是同构的。它检查的每对集合的运行时间是 O(K^2)，你需要检查 O(S^2) 个集合，所以你最终得到 O(S^2 * K^2 * N).
PS：我在这里假设“将A映射到B”你的意思是在排列组合下进行映射，所以P(a)实际上是排列P 由排列 a 组成，我已经使用了这样一个事实，即如果 P 是一个排列，那么必须存在一个 i 对于 Pa = b_i一些 a.
编辑 我决定取消删除我的答案，因为我不相信基于搜索的前一个 (@Jean Logeart) 是正确的。如果是，我会很乐意删除我的，因为它表现更差，但我想我有一个反例，请参阅 Jean 的回答下面的评论。
您可以排序比较：
// 1 - sort each set of permutation
for i = 0 to S-1
sort(pset[i])
// 2 - sort the array of permutations itself
sort(pset)
// 3 - compare
for i = 1 to S-1 {
if(areEqual(pset[i], pset[i-1]))
// pset[i] and pset[i-1] are isomorphic
}
一个具体的例子：
0: [[1,2,3],[3,2,1]]
1: [[2,3,1],[1,3,2]]
2: [[1,2,3],[2,3,1]]
3: [[3,2,1],[1,2,3]]
1 之后：
0: [[1,2,3],[3,2,1]]
1: [[1,3,2],[2,3,1]] // order changed
2: [[1,2,3],[2,3,1]]
3: [[1,2,3],[3,2,1]] // order changed
2 之后：
2: [[1,2,3],[2,3,1]]
0: [[1,2,3],[3,2,1]]
3: [[1,2,3],[3,2,1]]
1: [[1,3,2],[2,3,1]]
3 之后：
(2, 0) not isomorphic
(0, 3) isomorphic
(3, 1) not isomorphic
复杂度如何？
- 1 是
O(S * (K * N) * log(K * N)) - 2 是
O(S * K * N * log(S * K * N)) - 3 是
O(S * K * N)
所以整体复杂度是O(S * K * N log(S * K * N))
假设s1,s2\in S的两个元素是同构的。那么如果 p1 和 p2 是排列，那么 s1 同构于 s2 iff p1(s1) 同构于 p2(s2) 其中 pi(si) 是通过将 pi 应用于 si 中的每个元素而获得的排列集。
对于 1...s 中的每个 i 和 1...k 中的每个 j，选择 si 的第 j 个成员，并找到将其变为统一的排列。将其应用于 si 的所有元素。将每个 k 排列散列为一个数字，获得 k 个数字，对于 i 和j，成本 nk。
比较 i 和 j 两个不同值的散列集是 k^2 < nk。因此，您可以找到成本为 s^2 k^3 n 的候选匹配集。如果实际匹配数很少，则整体复杂性远低于您在问题中指定的值。
要检查两个集合 S₁ 和 S₂ 是否同构，您可以进行更短的搜索。
如果它们是同构的，则有一个排列 t 将 S₁ 的每个元素映射到 的一个元素S2；要找到 t 你可以选择 S₁ 的任何固定元素 p 并考虑排列
t₁ = (1/p) q₁
t₂ = (1/p) q₂
t₃ = (1/p) q₃
...
对于 S2 的所有元素 q。因为，如果存在有效的 t，则它必须将元素 p 映射到 S₂ 的元素，所以只有映射 p 到 S2 的元素的排列是可能的候选者。
此外，给定一个候选人 t 来检查两组排列是否 S₁t 和 S₂相等时，您可以使用计算出的散列作为每个元素的散列码的 x 或，仅当散列匹配时才对所有排列进行全面检查。
对此有一个非常简单的解决方案：换位。
如果两个集合同构，则表示存在one-to-one映射，集合S1中索引i处所有数字的集合等于所有数字的集合在集合 S2 中的某个索引 k 处。我的推测是没有两个non-isomorphic集有这个属性.
(1) Jean Logeart 的例子：
0: [[1,2,3],[3,2,1]]
1: [[2,3,1],[1,3,2]]
2: [[1,2,3],[2,3,1]]
3: [[3,2,1],[1,2,3]]
Perform ONE pass:
Transpose, O(n):
0: [[1,3],[2,2],[3,1]]
Sort both in and between groups, O(something log something):
0: [[1,3],[1,3],[2,2]]
Hash:
"131322" -> 0
...
"121233" -> 1
"121323" -> 2
"131322" -> already hashed.
0 and 3 are isomorphic.
(2) vsoftco 的 counter-example 在他对 Jean Logeart 的回答的评论中：
A = [ [0, 1, 2], [2, 0, 1] ]
B = [ [1, 0, 2], [0, 2, 1] ]
"010212" -> A
"010212" -> already hashed.
A and B are isomorphic.
您可以将每个集合变成 transposed-sorted 字符串或散列或任何压缩对象以进行 linear-time 比较。请注意，此算法将所有三个集合 A、B 和 C 视为同构，即使一个 p 将 A 转换为 B 而另一个 p 将 A 转换为 C。显然，在这种情况下，有 p 可以将这三个集合中的任何一个转换为另一个集合，因为我们所做的只是将一个集合中的每个 i 移动到特定的 k在另一个。如果像您所说的那样，您的目标是 "remove isomorphic permutations," 您仍然会得到要删除的集合列表。
解释：
假设在排序后的哈希中，我们记录了每个 i 来自哪个排列。 vsoftco 的 counter-example:
010212 // hash for A and B
100110 // origin permutation, set A
100110 // origin permutation, set B
为了确认同构，我们需要证明 i 在第一组的每个索引中分组移动到第二组中的 一些 索引，哪个索引无关紧要。对 i 的组进行排序不会使解决方案无效，而是用于确认集合之间的 movement/permutation。
现在根据定义，哈希 中的每个数字和哈希 中每个组中的每个数字在原始排列中对每个集合恰好表示一次。然而，我们选择在散列中排列每组 i 中的数字，我们保证该组中的每个数字代表集合中的不同排列；在我们理论上分配该数字的那一刻，我们保证它是 "reserved" 仅用于该排列和索引。对于给定的数字，比如2，在两个哈希中，我们保证它来自集合A中的一个索引和排列，而在第二个哈希中对应于集合[中的一个索引和排列=19=]。这就是我们真正需要展示的全部 - 一组（一组不同的 i's）中每个排列的一个索引中的数字仅在 一个索引 中另一组（一组不同的k）。数字属于哪个排列和索引是无关紧要的。
请记住，任何与集合 S1 同构的集合 S2 都可以使用一个置换函数或应用于 [=15= 的不同置换函数的各种组合从 S1 导出]的成员。我们的数字和组的排序或重新排序实际上代表的是我们选择分配作为同构解决方案的排列，而不是实际分配哪个数字来自哪个索引和排列。这里又是 vsoftco 的 counter-example，这次我们将添加哈希的原始索引：
110022 // origin index set A
001122 // origin index set B
因此我们的permutation同构的解是：
或者，按顺序：
（请注意，在 Jean Logeart 的示例中，同构的解决方案不止一种。）