我有一个数组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的解决方案将是优选的。

感谢您的帮助。

有帮助吗?

解决方案

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

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

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

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

许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top