寻找同构置换集的算法

Question

我有一组排列的数组，我想移除同构排列。

我们有 S 组排列，其中每个集合包含 K 个排列，每个排列表示为 N 个元素的数组。我目前将其保存为数组int pset[S][K][N]，其中S，K和N是固定的，N大于K。

如果存在将元素从< code>A转换为< code>B的置换< code>P，则两组置换< code>A和< code>B是同构的(例如，如果< code>a是集合< code>A的元素，则< code>P(a)是集合< code>B的元素)。在这种情况下，我们可以说< code>P使得< code>A和< code>B同构。

我目前的算法是：

< li >我们选择所有对< code>s1 = pset[i]和< code>s2 = pset[j]，因此< code>i

这个算法的工作速度非常慢：O（S^2）是第一步，O（K！）循环遍历每个排列T，O（N^2）找到R，O（K*N）检查R是否是使s1和s2同构的排列 - 所以它是O（S^2 * K！ * N^2）。

问题:我们能让它更快吗？

Answer 1

假设S中s1， s2\的两个元素是同构的。然后如果p1和p2是排列，那么s1与s2同构，如果p1（s1）与p2（s2）同构，其中pi（si）是通过将pi应用于si中的每个元素而获得的排列集。

对于 1...s 中的每个 i 和 1...k 中的每个 i，选择 si 的第 j 个成员，并找到将其更改为单位的排列。将其应用于 si 的所有元素。将每个 k 排列散列为一个数字，得到 k 个数字，用于 i 和 j 的任何选择，成本为 nk。

比较I和j的两个不同值的散列集合是k^2

Answer 2

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

如果两个集合是同构的，则意味着存在一对一映射，其中集合 S1 中索引 i 处的所有数字的集合等于集合 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。显然，在这种情况下，有ps将这三个集合中的任何一个转换为另一个，因为我们所做的是将一个集合中每个i移动到另一个集合的特定k。如您所述，如果您的目标是“移除同构排列”，您仍然会得到一个要移除的集合列表。

说明：

假设与排序的散列一起，我们记录了每个i来自哪个排列。vsoftco的反例：

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

为了确认同构，我们需要证明从第一个集合到每个索引分组的i移动到第二个集合中的某个索引，哪个索引无关紧要。对 i 的组进行排序不会使解失效，而是用于确认集合之间的移动/排列。

现在根据定义，散列中的每个数和散列中每个组中的每个数在原点排列中对于每个集合仅被表示一次。然而，我们选择在散列中排列每组< code>i中的数字，我们保证该组中的每个数字代表集合中的不同排列；当我们从理论上分配这个数字时，我们保证它只为那个排列和索引“保留”。对于给定的数，比如说< code>2，在两个散列中，我们保证它来自集合< code>A中的一个索引和置换，并且在第二个散列中对应于集合< code>B中的一个索引和置换。这就是我们真正需要展示的——一个集合(一组不同的< code>i)中的每个排列的一个索引中的数字只到另一个集合(一组不同的< code>k)中的一个索引。数字属于哪个排列和索引无关紧要。

请记住，与setS1同构的任何集合S2都可以使用一个置换函数或应用于S1成员的不同置换函数的各种组合从S1派生出来。我们的数字和组的排序或重新排序实际上代表的是我们选择分配的置换作为同构的解决方案，而不是实际分配哪个数字来自哪个索引和置换。这又是vsoftco的反例，这次我们将添加哈希的原始索引：

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

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

或者，按顺序：

（请注意，在Jean Logeart的例子中，同构有多个解决方案。）

Answer 3

您可以排序和比较：

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