从列表的元素中查找互斥集的python组合

Question

在我目前正在开展的一个项目中,我已经实现了我希望程序执行的大约80%,我对结果非常满意.

在剩下的20%中,我遇到了一个问题,让我有点困惑如何解决.这里是:

我想出了一个包含几个数字(任意长度)的列表列表例如:

listElement[0] = [1, 2, 3]
listElement[1] = [3, 6, 8]
listElement[2] = [4, 9]
listElement[4] = [6, 11]
listElement[n] = [x, y, z...]

其中n可达到40,000左右.

假设每个列表元素是一组数字(在数学意义上),我想要做的是导出互斥集的所有组合; 也就是说,就像上面列表元素的powerset一样,但排除了所有非不相交集元素.

因此,为了继续n = 4的示例,我想提出一个具有以下组合的列表:

newlistElement[0] = [1, 2, 3]
newlistElement[1] = [3, 6, 8]
newlistElement[2] = [4, 9]
newlistElement[4] = [6, 11] 
newlistElement[5] = [[1, 2, 3], [4, 9]]
newlistElement[6] = [[1, 2, 3], [6, 11]]
newlistElement[7] = [[1, 2, 3], [4, 9], [6, 11]]
newlistElement[8] = [[3, 6, 8], [4, 9]]
newlistElement[9] = [[4, 9], [6, 11]

例如,无效的情况是组合[[1,2,3],[3,6,8]],因为3在两个元素中是常见的.有没有优雅的方法来做到这一点？我会非常感谢任何反馈.

我还必须指定我不想做powerset函数,因为初始列表可能有相当多的元素(正如我所说n可以达到40000),并且使用如此多元素的powerset永远不会完成.

Answer 1

下面的程序中使用的方法类似于之前的几个答案，排除不相交的集合，因此通常不测试所有组合。它与以前的答案不同，它会尽早贪婪地排除所有可以排除的集合。这使得它的运行速度比 NPE 的解决方案快几倍。以下是两种方法的时间比较，使用具有 200, 400, ... 1000 个大小为 6 的集合（元素范围为 0 到 20）的输入数据：

\n\n

Set size =   6,  Number max =  20   NPE method\n  0.042s  Sizes: [200, 1534, 67]\n  0.281s  Sizes: [400, 6257, 618]\n  0.890s  Sizes: [600, 13908, 2043]\n  2.097s  Sizes: [800, 24589, 4620]\n  4.387s  Sizes: [1000, 39035, 9689]\n\nSet size =   6,  Number max =  20   jwpat7 method\n  0.041s  Sizes: [200, 1534, 67]\n  0.077s  Sizes: [400, 6257, 618]\n  0.167s  Sizes: [600, 13908, 2043]\n  0.330s  Sizes: [800, 24589, 4620]\n  0.590s  Sizes: [1000, 39035, 9689]\n

\n\n

在上面的数据中，左列显示执行时间（以秒为单位）。数字列表显示发生了多少个单联合、双联合或三联合。程序中的常量指定数据集的大小和特征。

\n\n

#!/usr/bin/python\nfrom random import sample, seed\nimport time\nnsets,   ndelta,  ncount, setsize  = 200, 200, 5, 6\ntopnum, ranSeed, shoSets, shoUnion = 20, 1234, 0, 0\nseed(ranSeed)\nprint \'Set size = {:3d},  Number max = {:3d}\'.format(setsize, topnum)\n\nfor casenumber in range(ncount):\n    t0 = time.time()\n    sets, sizes, ssum = [], [0]*nsets, [0]*(nsets+1);\n    for i in range(nsets):\n        sets.append(set(sample(xrange(topnum), setsize)))\n\n    if shoSets:\n        print \'sets = {},  setSize = {},  top# = {},  seed = {}\'.format(\n            nsets, setsize, topnum, ranSeed)\n        print \'Sets:\'\n        for s in sets: print s\n\n    # Method by jwpat7\n    def accrue(u, bset, csets):\n        for i, c in enumerate(csets):\n            y = u + [c]\n            yield y\n            boc = bset|c\n            ts = [s for s in csets[i+1:] if boc.isdisjoint(s)]\n            for v in accrue (y, boc, ts):\n                yield v\n\n    # Method by NPE\n    def comb(input, lst = [], lset = set()):\n        if lst:\n            yield lst\n        for i, el in enumerate(input):\n            if lset.isdisjoint(el):\n                for out in comb(input[i+1:], lst + [el], lset | set(el)):\n                    yield out\n\n    # Uncomment one of the following 2 lines to select method\n    #for u in comb (sets):\n    for u in accrue ([], set(), sets):\n        sizes[len(u)-1] += 1\n        if shoUnion: print u\n    t1 = time.time()\n    for t in range(nsets-1, -1, -1):\n        ssum[t] = sizes[t] + ssum[t+1]\n    print \'{:7.3f}s  Sizes:\'.format(t1-t0), [s for (s,t) in zip(sizes, ssum) if t>0]\n    nsets += ndelta\n

\n\n

编辑：在函数中accrue，参数(u, bset, csets)使用如下：
\n\xe2\x80\xa2 u = 当前集合并集中的集合列表
\n\xe2\x80\xa2 bset = "big set" = u = 元素的平面值已使用
\n\xe2\x80\xa2 csets = 候选集 = 有资格包含的集列表
\n请注意，如果第一行accrue被替换为
\n def accrue(csets, u=[], bset=set()):
\n 并且第七行被替换为
\n for v in accrue (ts, y, boc):
\n（即，如果参数重新排序并为 u 和 bset 提供默认值），然后accrue可以通过调用[accrue(listofsets)]来生成其兼容联合列表。

\n\n

关于ValueError: zero length field name in format评论中提到的使用Python 2.6时发生的错误，请尝试以下操作。

\n\n

# change:\n    print "Set size = {:3d}, Number max = {:3d}".format(setsize, topnum)\n# to:\n    print "Set size = {0:3d}, Number max = {1:3d}".format(setsize, topnum)\n

\n\n

程序中的其他格式可能需要类似的更改（添加适当的字段编号）。请注意，2.6 页面中的新增内容显示 \xe2\x80\x9c 对 str.format() 方法的支持已向后移植到 Python 2.6\xe2\x80\x9d。虽然它没有说明字段名称或数字是否是必需的，但它没有显示没有它们的示例。相比之下，这两种方式都适用于 2.7.3。

\n