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

的一个元素中找到该对元素。我怎样才能做到这一点？

LE：总是q < k

Answer 1

如果我理解正确的话，你想要组成最少 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 group the least
        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'}]