python - 最大化形成交集的集合数

Question

假设我有 10 组，每组都有一些随机数量的正整数。

现在，我想最大化可以形成交集的集合的数量(不搜索最大的交集)，考虑到一个集合只能与另一个集合形成交集的约束，前提是至少有“x”个整数重叠。例如，如果 x = 2，则 [1,2,3,4] 不能与 [1,5,6,7]< 形成交集 因为只有 1 个整数重叠，而不是 2 个。

另一件需要注意的事情(虽然很明显)是，对于 x=2，如果我有 [1,2,3,4] 和 [1 ,2,6,7]，交集可以发生，对于第三个集合形成交集，它必须在集合中的某处有 [1,2]。

我无法正确地形成一个算法来执行此操作，因为可以以指数方式比较这些集合!即使我只有 3 个集合，给定集合的大小，我也必须考虑给定交集约束的每个子集组合比较。

我正在生成我的集合如下:

sets = []
for i in range(0,10):
    temp = np.random.randint(1,3000)
    sets.append(set(np.random.randint(1, 3000, temp)))

Answer 1

您可以计算集合中每个数字出现的次数。由于您正在尝试最大化交叉点的总数，因此最常见的数字将导致最大数量的可能交叉点(理想情况下每 2 个集合形成一个交叉点)。这是相关代码:

import numpy as np

# Set a seed for testing purposes
np.random.seed(1)

# Initialise the min number of elements in an intersection
x = 2

# Initialise the list of sets
sets = list()

# Initialise the count mapping
count = dict()

# Generate the sets
for i in range(0,10):
    temp = np.random.randint(1,3000)
    sets.append(set(np.random.randint(1, 3000, temp)))

# Count each number's occurrence
for s in sets:
    for number in s:
        if number in count:
            count[number] +=1
        else:
            count[number] = 1

# Sort the result (by the count number)
l = sorted(count, key=lambda x: count[x], reverse=True)

# Print the number of occurrences (within the boundary of min x elements)
print(count[l[x-1]])

# Print the numbers that give you the maximum number of intersections
print(l[:x])

结果是:

7
[2270, 2225]

在这种情况下，10 个集合中有 7 个包含数字 2270 和 2225，因此可以形成总共 21 (6*7/2) 个交叉点。性能应该是 O(NlogN)(由于排序)，其中 N 是数字的总数。