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

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

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

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

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

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

编辑： 在函数中

accrue

，参数

(u, bset, csets)

按如下方式使用：
•u =当前集合联合中的集合列表
•bset =“大集合” = u的固定值=已使用的元素
•csets =候选集合=符合条件的集合列表included包括在内，
请注意，如果用的第一行

accrue

替换为

def accrue(csets, u=[], bset=set()):

，第七行替换为

for v in accrue (ts, y, boc):

（即，如果参数已重新排序，并且给u和bset提供了默认值），则

accrue

可以通过调用

[accrue(listofsets)]

它以生成其兼容并集的列表。

关于

ValueError: zero length field name in format

在使用Python
2.6时出现的注释中提到的错误，请尝试以下 *** 作。

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

程序中的其他格式可能需要进行类似的更改（添加适当的字段编号）。请注意，2.6页中的新增内容是“对str.format（）方法的支持已反向移植到Python
2.6”。虽然没有说是否需要字段名称或数字，但没有显示没有它们的示例。相比之下，两种方法在2.7.3中均有效。