python - 来自多个列表的元素的最小组合，使得所有元素至少出现一次

Question

所以我遇到的问题是:

有多个组，每个组包含多个个体和一个等级。例如

GroupA = [('Joe', 1), ('Kate', 2), ('Jeff', 1)]
GroupB = [('Sam', 1), ('Jim', 2), ('Stephanie', 2)]
GroupCC = [('Adam', 2), ('David', 1), ('Liz', 1), ('Michael', 2)]

• 我正在组建多个团队，每个团队只包含一个人，因此每个团队包含 3 个人。前任。 ['凯特'、'山姆'、'亚当']

• 一个人可以属于多个团队，但是排名第一的人应该有优先权。如果有多个排名为 1 的人，则应该平均分配。

我最少可以组建多少支球队，让每个球员都属于一个球队？

在这种情况下，显而易见的答案是 4 个队，因为 listC 的元素最多。这也意味着 listA 和 list B 中的某个人将被包含两次。我想确保使用两次的人是列表 A 中的 Joe 或 Jeff，以及列表 B 中的 Sam。

Answer 1

首先，让我们将其推广到任意数量的组

GroupA = [('Joe', 1), ('Kate', 2), ('Jeff', 1)]
GroupB = [('Sam', 1), ('Jim', 2), ('Stephanie', 2)]
GroupC = [('Adam', 2), ('David', 1), ('Liz', 1), ('Michael', 2)]
groups = [GroupA, GroupB, GroupC]

然后我们将迭代这些组，并根据需要重复元素(优先考虑 1)。我们还将去除列表中每个元素的等级。

max_len = max(map(len, groups))

names = []
for group in groups:
    subgroup = list(group)
    if any(rank == 1 for _, rank in group):
        subgroup = list(filter(lambda x:x[1] == 1, group))
    group += subgroup * (max_len - len(group))
    names.append([name for name, _ in group])

现在名称包含名称列表，名称至少重复必要的次数以匹配最长的组(可能更多，zip 将修剪)。

我们会知道将这些列表压缩在一起，并获得我们的团队。

teams = list(zip(*names))

结果:

>>> print("\n".join(map(str, teams)))
('Joe', 'Sam', 'Adam')
('Kate', 'Jim', 'David')
('Jeff', 'Stephanie', 'Liz')
('Joe', 'Sam', 'Michael')