比较起来子集的集合，以置换

Question

我有一个数组a [i] [j]。元素是炭，解释为集的子集{1，...，8}（元素k是在该子集中，如果第k个位是1）。我不认为这是相关的，但每一个元素都只有4位设置。

每一行一个[1] [j]的一个.. [N] [j]为的子集的集合{1，...，8}。我需要删除重复的行，其中的两行被视为重复，如果一个可从其它通过的置换来获得{1，...，8}。

实施例（0bxxxxxxxx意味着二进制数）：

0b11000000, 0b01100000, 0b00110000

是一个重复的

0b00110000, 0b00011000, 0b00100100

，因为前者可从后者通过应用置换来获得

8->8, 7->7, 6->1, 5->4, 4->3, 3->2, 2->5, 1->6

和重排序的结果。

有关性能方面的考虑，该阵列包含约2000行，每行包含至多20个元素。每一行已经订购，也行是按照字典递增顺序，如果可能的帮助。该算法的其余部分是用C，所以一个C的解决方案将是优选的。

感谢您的帮助。

Answer 1

如果所有子集有2个元件，这将代表图同构时，与子集表示图的边。 这更是一般的（因此很可能更难），所以我想看看用来解决图同构，看看启发他们是否适用于此。

有很多图形同构的启发式可以廉价地排除同构的。对于特定集合，可以计算出有多少子集并的每个元素都属于，那么那种。在你的榜样，两者的集合会得到[2,2,1,1,0,0,0,0]。如果两个集合的排序顺序是不同的，那么就没有同构。当然，平等并不能保证有。

有许多是即使在筛分出非同构好图（并有可能在这里适用）更类似于试探。

另外，8！只有40320，所以暴力破解所有排列是不完全不可行的。