找到同构置换集的算法

Question

我有一组排列,我想删除同构排列.

我们有多S组排列,其中每组包含K排列,每个排列表示为N元素和数组.我目前正在将其保存为数组int pset[S][K][N],其中S,K并且N是固定的,并且N大于K.

两组排列,A并且B,如果存在排列,则是同构的,P将元素转换A为B(例如,if a是元素的集合A,然后P(a)是集合的元素B).在这种情况下,我们可以说P制造A和B同构.

我目前的算法是:

1. 我们选择所有对s1 = pset[i]和s2 = pset[j],使得i < j
2. 从choosen集(每个元素s1和s2)从numered 1到K.这意味着每个元素都可以表示为s1[i]或s2[i],在哪里0 < i < K+1
3. 对于每一个排列T的K元素,我们做到以下几点:
   • 找到排列R,这样R(s1[1]) = s2[1]
   • 检查是否R是一个构造s1和T(s2)同构的排列,其中T(s2)是元素的重新排列(排列)s2,所以基本上我们只检查是否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).

问题:我们可以加快速度吗？

Answer 1

您可以排序和比较:

// 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))

Answer 2

对此有一个非常简单的解决方案:换位.

如果两个集是同构的,则意味着存在一对一映射,其中集合中索引处的所有数字的i集合S1等于集合中某个索引处的所有数字的k集合S2.我的猜想是没有两个非同构集具有这个属性.

(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在他对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.

您可以将每个集合转换为转置排序的字符串或散列或任何压缩对象,以进行线性时间比较.请注意,此算法考虑了所有三组A,B并且C即使作为一个同构p转换A到B与另一p转换A到C.很明显,在这种情况下,有ps将这三组中的任何一组转换为另一组,因为我们所做的只是将i一组中的每一组移动到另一组中的特定组k.如果按照您的说法,您的目标是"删除同构排列",那么您仍会获得要删除的集合列表.

说明:

假设与我们的排序哈希一起,我们保留了每个i来自哪个排列的记录.vsoftco的反例:

010212  // hash for A and B
100110  // origin permutation, set A
100110  // origin permutation, set B

为了确认同构,我们需要证明i在第一组中每个索引中的分组移动到第二组中的某个索引,该索引无关紧要.对组的排序i不会使解决方案无效,而是用于确认组之间的移动/置换.

现在根据定义,散列中的每个数字和散列中每个组中的每个数字在原始排列中以每个集合恰好一次表示.但是我们选择i在散列中的每个组中排列数字,我们保证该组中的每个数字代表集合中的不同排列; 当我们理论上分配该数字时,我们保证它仅为该排列和索引"保留".对于给定数字,例如2,在两个哈希中,我们保证它来自集合中的一个索引和置换A,并且在第二个哈希中对应于集合中的一个索引和置换B.这就是我们真正需要展示的 - 一个集合中的每个排列的一个索引中的数字(一组不同i的)仅在另一个集合(一组不同k的集合)中转到一个索引.数字所属的排列和索引是无关紧要的.

请记住,任何要设置的S2同构集S1都可以S1使用一个置换函数或应用于S1成员的不同置换函数的各种组合来派生.我们的数字和组实际表示的排序或重新排序是我们选择分配为同构的解的排列,而不是实际分配哪个数来自哪个索引和排列.这里再次是vsoftco的反例,这次我们将添加哈希的原始索引:

110022 // origin index set A
001122 // origin index set B

因此,我们的排列,同构的解决方案是:

或者,按顺序:

(请注意,在Jean Logeart的例子中,同构的解决方案不止一个.)