проблема
У меня есть группа людей, и я хочу, чтобы каждый человек имел встречу 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теперь содержит только пары, которые не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 человек :) Это просто простой пример, который представляет проблему совпадения/комбинаторики, которую я пытаюсь решить.
