下面的程序中使用的方法在排除不相交的集合方面类似于之前的几个答案,因此通常不会测试所有组合。它与先前的答案不同,它尽早贪婪地排除了所有可能的集合。这使其运行速度比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/python
from random import sample, seed
import time
nsets, ndelta, ncount, setsize = 200, 200, 5, 6
topnum, ranSeed, shoSets, shoUnion = 20, 1234, 0, 0
seed(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中均有效。