Задача
У меня есть группа людей, и я хочу, чтобы каждый человек имел встречу 1: 1 с каждым другим человеком в группе. Данный человек может встречаться только с одним человеком одновременно, поэтому я хочу сделать следующее:
- Найдите все возможные комбинации
- Сгруппируйте пары в «раунды» собраний, где каждый человек может участвовать в раунде только один раз, и в раунде должно быть как можно больше пар, чтобы удовлетворить все возможные комбинации пар в наименьшем количестве раундов.
Чтобы продемонстрировать проблему с точки зрения желаемого ввода / вывода, допустим, у меня есть следующий список:
>>> people = ['Dave', 'Mary', 'Susan', 'John']
Я хочу получить следующий вывод:
>>> for round in make_rounds(people):
>>> print(round)
[('Dave', 'Mary'), ('Susan', 'John')]
[('Dave', 'Susan'), ('Mary', 'John')]
[('Dave', 'John'), ('Mary', 'Susan')]
Если бы у меня было нечетное количество людей, я бы ожидал такого результата:
>>> people = ['Dave', 'Mary', 'Susan']
>>> for round in make_rounds(people):
>>> print(round)
[('Dave', 'Mary')]
[('Dave', 'Susan')]
[('Mary', 'Susan')]
Ключом к этой проблеме является то, что мне нужно, чтобы мое решение было эффективным (в пределах разумного). Я написал код, который работает , но с ростом people он становится экспоненциально медленным. Я не знаю достаточно о написании эффективных алгоритмов, чтобы знать, неэффективен ли мой код или я просто связан параметрами задачи
Что я пробовал
Шаг 1 прост: я могу получить все возможные пары, используя itertools.combinations:
>>> from itertools import combinations
>>> people_pairs = set(combinations(people, 2))
>>> print(people_pairs)
{('Dave', 'Mary'), ('Dave', 'Susan'), ('Dave', 'John'), ('Mary', 'Susan'), ('Mary', 'John'), ('Susan', 'John')}
Чтобы отработать сами раунды, я строю раунд примерно так:
- Создать пустой
round список
- Перебрать копию набора
people_pairs, вычисленного с использованием метода combinations, описанного выше
- Для каждого человека в паре проверьте, существуют ли какие-либо существующие пары в текущем
round, которые уже содержат этого человека
- Если уже есть пара, содержащая одного из индивидов, пропустите эту пару для этого раунда. Если нет, добавьте пару в раунд и удалите пару из списка
people_pairs.
- Как только все пары людей будут перебраны, добавьте раунд к мастеру
rounds список
- Начните снова, поскольку
people_pairs теперь содержит только пары, которые не прошли в первый раунд
В конце концов это приводит к желаемому результату и сокращает мои пары людей, пока не останется ни одного и все раунды не будут рассчитаны. Я уже вижу, что это требует смешного количества итераций, но я не знаю лучшего способа сделать это.
Вот мой код:
from itertools import combinations
# test if person already exists in any pairing inside a round of pairs
def person_in_round(person, round):
is_in_round = any(person in pair for pair in round)
return is_in_round
def make_rounds(people):
people_pairs = set(combinations(people, 2))
# we will remove pairings from people_pairs whilst we build rounds, so loop as long as people_pairs is not empty
while people_pairs:
round = []
# make a copy of the current state of people_pairs to iterate over safely
for pair in set(people_pairs):
if not person_in_round(pair[0], round) and not person_in_round(pair[1], round):
round.append(pair)
people_pairs.remove(pair)
yield round
График эффективности этого метода для списков размером 100-300 с использованием https://mycurvefit.com показывает, что вычисление раундов для списка из 1000 человек, вероятно, займет около 100 минут. Есть ли более эффективный способ сделать это?
Примечание: я не на самом деле пытаюсь организовать встречу из 1000 человек :) Это всего лишь простой пример, который представляет проблему сопоставления / комбинаторики, которую я пытаюсь решить.