n选k与n选q的最小案例数

Question

我有一个列表

people = ['P1', 'P2', 'P3', 'P4', 'P5', 'P6', 'P7']

allComb4 = list(itertools.combinations(people,4)) # n choose k
#[('P1', 'P2', 'P3', 'P4'), ('P1', 'P2', 'P3', 'P5'), ('P1', 'P2', 'P3', 'P6'), ('P1', 'P2', 'P3', 'P7'), ('P1', 'P2', 'P4', 'P5'), ('P1', 'P2', 'P4', 'P6'), ('P1', 'P2', 'P4', 'P7'), ('P1', 'P2', 'P5', 'P6'), ('P1', 'P2', 'P5', 'P7'), ('P1', 'P2', 'P6', 'P7'), ('P1', 'P3', 'P4', 'P5'), ('P1', 'P3', 'P4', 'P6'), ('P1', 'P3', 'P4', 'P7'), ('P1', 'P3', 'P5', 'P6'), ('P1', 'P3', 'P5', 'P7'), ('P1', 'P3', 'P6', 'P7'), ('P1', 'P4', 'P5', 'P6'), ('P1', 'P4', 'P5', 'P7'), ('P1', 'P4', 'P6', 'P7'), ('P1', 'P5', 'P6', 'P7'), ('P2', 'P3', 'P4', 'P5'), ('P2', 'P3', 'P4', 'P6'), ('P2', 'P3', 'P4', 'P7'), ('P2', 'P3', 'P5', 'P6'), ('P2', 'P3', 'P5', 'P7'), ('P2', 'P3', 'P6', 'P7'), ('P2', 'P4', 'P5', 'P6'), ('P2', 'P4', 'P5', 'P7'), ('P2', 'P4', 'P6', 'P7'), ('P2', 'P5', 'P6', 'P7'), ('P3', 'P4', 'P5', 'P6'), ('P3', 'P4', 'P5', 'P7'), ('P3', 'P4', 'P6', 'P7'), ('P3', 'P5', 'P6', 'P7'), ('P4', 'P5', 'P6', 'P7')]

allComb2 = list(itertools.combinations(people,2)) # n choose q
# [('P1', 'P2'), ('P1', 'P3'), ('P1', 'P4'), ('P1', 'P5'), ('P1', 'P6'), ('P1', 'P7'), ('P2', 'P3'), ('P2', 'P4'), ('P2', 'P5'), ('P2', 'P6'), ('P2', 'P7'), ('P3', 'P4'), ('P3', 'P5'), ('P3', 'P6'), ('P3', 'P7'), ('P4', 'P5'), ('P4', 'P6'), ('P4', 'P7'), ('P5', 'P6'), ('P5', 'P7'), ('P6', 'P7')]

我需要在 allComb4 中找到与 allComb2 相比的最少元素数量。想要的结果如下。

output = [['P1', 'P2', 'P5', 'P6'], ['P1', 'P3', 'P4', 'P7'], ['P2', 'P3', 'P5', 'P7'], ['P2', 'P4', 'P5', 'P6'], ['P3', 'P4', 'P6', 'P7']]

这意味着，我从 allComb2 中选出的任何一对，我都能在 output 的一个元素中找到这对元素。我该怎么做呢？

补充说明：总是 q < k

Answer 1

import itertools, math

E = 7 # number of elements
K = 4 # E choose K
Q = 3 # E choose Q

# construct list
a = [x for x in range(1, E+1)]

# construct combinations
allCombQ = list(itertools.combinations(a,Q))
allCombK = list(itertools.combinations(a,K))

# start iteration
iteration = 1
coverDone = False
while not coverDone:
    iteration += 1
    if iteration > len(allCombK):
        break
    print("Iteration: ", iteration)

    # scan combinations `len(allCombK)` choose `iteration`
    for sublist in itertools.combinations([x for x in range(len(allCombK))], iteration):
        sublist = list(sublist)
        sublistFound = True

        # check if every element of set of allComb2 exists in subslist (construct above)
        for subCombQ in allCombQ:
            subCombQ = list(subCombQ)
            foundInK = False
            for subCombK in sublist:
                subCombK = list(allCombK[subCombK])
                check = all(item in subCombK for item in subCombQ)
                if check:
                    foundInK = True
                    break
            if not foundInK:
                sublistFound = False
                break
        if sublistFound:
            coverDone = True
            break

for i in sublist:
    print(allCombK[i])

当Q等于2的时候，程序大约需要几秒钟就能完成。

但是当Q等于3的时候，程序还在运行，已经快90分钟了。

如果有任何优化的方法，欢迎分享。

Answer 2

如果我理解得没错，你想要组成最少数量的4人小组，确保每对人至少在一个小组里出现过。

如果是这样，这里有一个实现的例子：

people = {'P1', 'P2', 'P3', 'P4', 'P5', 'P6', 'P7'}
people_total = len(people)

group_total = 4  # size of groups we want to constitute

visited_persons = {
    person: {person}
    for person in people
}

minimum_groups = []

while any(len(v) < people_total for v in visited_persons.values()):  # while there is someone who hasn't visited another person
    # take the person who has visited the least
    person = min(people, key=lambda p: (len(visited_persons[p]), p))

    # start a new group with this person
    group = {person}
    while len(group) < group_total:
        # find the person which knowns the least people
        person = min(people - group, key=lambda p: len(visited_persons[p] & group))

        # save visits
        for other in group:
            visited_persons[person].add(other)
            visited_persons[other].add(person)

        group.add(person)

    minimum_groups.append(group)

print(minimum_groups)

它会输出 [{'P1', 'P3', 'P4', 'P2'}, {'P1', 'P6', 'P5', 'P7'}, {'P7', 'P5', 'P4', 'P2'}, {'P5', 'P6', 'P3', 'P7'}, {'P1', 'P4', 'P6', 'P2'}]

这个方法的思路是一个一个地建立小组，同时记录每个人访问过谁，存储在 visited_persons 里。我们通过选择访问过最少人的那个人来创建一个新小组。然后，我们再把在这个小组里访问过其他人最少的人加入到这个小组里。