比较直至排列的子集集合

Question

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

每行a [1] [j] .. a [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个元素，则这将代表graph isomorphism，子集表示图形边缘。 这更加普遍（因此可能更难），所以我会看看用于解决图同构的启发式算法，看看它们是否适用于此。

有许多图形同构启发式算法可以便宜地排除同构。对于特定的集合，您可以计算每个元素所属的子集数量，然后对其进行排序。在你的例子中，两个集合都会得到[2,2,1,1,0,0,0,0]。如果两个集合的排序顺序不同，那么就没有同构。当然，平等并不能保证存在。

还有很多类似的启发式算法在筛选非同构图（甚至可能适用于此）方面更胜一筹。

另外，8！仅仅是40320，所以强制所有的排列并不是完全不可行的。