这里是使用
itertools
的方法来完成您所称的
迭代 1
的第一部分。如果有可能运行它,那么您可以在循环中反复运行它,在每个阶段删除找到的项。正如我在评论中指出的那样,它只适用于小的
n
。
import itertools
def intersect(sets):
I = sets[0].copy()
for s in sets[1:]:
I = I & s
return I
def largestIntersection(sets,n):
maxSize = 0
maxSets = [set()]
for groupCombo in itertools.combinations(sets,n):
I = intersect(groupCombo)
if len(I) > maxSize:
maxSize = len(I)
maxSets = [I]
elif len(I) == maxSize:
maxSets.append(I)
return maxSets
例如:
>>> groups = [
[1],
[1, 2 ,3],
[1, 2, 3, 4, 5],
[1, 2, 3 ,4],
[2, 3],
[4, 5, 6],
[4, 5, 7]
]
>>> groups = [set(group) for group in groups]
>>> largestIntersection(groups,3)
[{1, 2, 3}]
编辑:以下修改可能有所帮助——取决于组中数字的分布和组的大小:
def guessSize(sets,n,trials):
return max(len(intersect(random.sample(sets,n))) for trial in range(trials))
def maxIntersection(sets,n,trials = 100000):
k = guessSize(sets,n,trials)
filteredSets = [s for s in sets if len(s) >= k]
return largestIntersection(filteredSets,n)
首先,想法是在尝试遍历交集之前先减少组的数量。例如:
import random
nums = list(range(1,101))
testGroups = [set(random.sample(nums,random.randint(1,100))) for n in range(1000)]
foundGroups = maxIntersection(testGroups,3)
如果我直接使用largestIntersection(testGroups)
,计算foundGroups
需要几分钟,但只需几秒钟。另一方面,如果随机参数选择不同,则时间节省变得微不足道。
进一步编辑: 也许您可以更加积极地过滤:
import collections
def maxIntersection(sets,n,trials = 100000):
k = guessSize(sets,n,trials)
filteredSets = [s for s in sets if len(s) >= k]
counts = collections.Counter()
for s in filteredSets:
for x in s:
counts[x] +=1
t = {x for x,c in counts.items() if c >= k}
filteredSets = [s & t for s in filteredSets if len(s & t) >= k]
return largestIntersection(filteredSets,n)
[4, 5]
是一组而[2, 3]
不是? - Yury TarabankoC(10000,10)
大约为2.7 x 10 ** 33。交集所有的10组集合的暴力方法行不通。所有组的联合有多大?(在您的示例中,它有7个项目)。如果与组的数量相比这个数字很小(如果存在许多重复),则有一些可以使用的想法。 - John Coleman