一种寻找同构排列集的算法

Question

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

我们有S排列集，其中每个集合都包含K置换，每个置换都表示为N元素的和数组。我目前将其保存为数组int pset[S][K][N]，其中S、K和N是固定的，N大于K。 两组排列( A和B )是同构的，如果存在置换P，则将元素从A转换为B (例如，如果a是set A的元素，那么P(a)是set B的元素)。在这种情况下，我们可以说P 使 A 和 B 同构。

我目前的算法是：

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

问:我们能快点吗？

Answer 1

有一个非常简单的解决方案:换位。

如果两个集合是同构的，则表示存在一对一映射，其中集合S1中索引k处的所有数集等于集合S2中某个索引k处的所有数集。我的猜想是，没有两个非同构集具有这种性质。

(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。显然，在这种情况下，有p将这三组中的任何一组转换为另一组，因为我们所做的就是将一个集合中的每个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's)中每个排列的索引中的一个索引中的数字，只在另一个集合(一组不同的k's)中转到一个索引。数字所属的置换和索引是无关的。

请记住，任何与集合S2同构的集合S1，都可以使用一个置换函数或应用于S1成员的各种不同排列函数的组合从S1导出。我们的数字和组的排序或重新排序实际上代表的是我们选择指定的置换，作为同构的解决方案，而不是对来自哪个索引和置换的数字的实际赋值。这里是vsoftco的反例，这一次我们将添加我们的散列的起源索引：

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

因此，我们的排列是同构的解决方案，它是：

​

​

或者，为了：

​

​

(请注意，在Jean的示例中，对同构有不止一个解决方案。)

Answer 2

您可以排序和比较：

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

走a0 in A。然后找到它的逆(fast，O(N))，叫它a0inv。然后在B中选择一些B，定义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)实际上是由置换a组成的置换P，我使用的事实是，如果P是置换，那么就必须存在一个i，对于某些a，Pa = b_i必须存在。

编辑我决定取消删除我的答案，因为我不相信之前的答案(@Jean )基于搜索是正确的。如果是，我会很乐意删除我的，因为它表现更差，但我想我有一个反例，见下面的评论让的答案。