Минимальные комбинации элементов из нескольких списков, чтобы все элементы появлялись хотя бы один раз - PullRequest
Новая
       13

Минимальные комбинации элементов из нескольких списков, чтобы все элементы появлялись хотя бы один раз

2 голосов
/ 08 марта 2019

Итак, у меня проблема в следующем:

Есть несколько групп, каждая из которых содержит несколько человек вместе со своим рангом.Например, 

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

  • Я собираю несколько команд, в состав которых входит ровно один человек из каждой группы, так что в каждой команде по 3 человека.ех.['Kate', 'Sam', 'Adam']

  • Один человек может принадлежать к нескольким командам, но люди с рангом 1 должны иметь приоритет.Если есть несколько человек с рангом 1, то оно должно быть равномерно распределено.

Какое минимальное количество команд, которые я могу собрать, чтобы каждый игрок принадлежал к команде?

В этом случае очевидный ответ - 4 команды, потому что listCимеет больше всего элементов.Это также означает, что будет один человек из списка А и списка Б, который будет включен дважды.Я хочу убедиться, что дважды использовался Джо или Джефф из списка А, а Сэм из списка Б.

1 Ответ

1 голос
/ 08 марта 2019

Во-первых, давайте обобщим это на любое количество групп 

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')
...