c++ - 寻找同构排列集的算法

Question

我有一组排列，我想删除同构排列。

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.

我目前的算法是:

1. 我们选择所有对s1 = pset[i]和 s2 = pset[j] ，这样 i < j
2. 所选集合(s1 和 s2)中的每个元素都从 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) .

Question: Can we make it faster?

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