Найти наиболее эффективные группы пар
проблема
У меня есть группа людей, и я хочу, чтобы каждый человек имел встречу 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 человек :) Это просто простой пример, который представляет проблему совпадения/комбинаторики, которую я пытаюсь решить.
Ответы
Ответ 1
Это реализация алгоритма, описанного в турнире Round-robin в Википедии.
from itertools import cycle , islice, chain
def round_robin(iterable):
items = list(iterable)
if len(items) % 2 != 0:
items.append(None)
fixed = items[:1]
cyclers = cycle(items[1:])
rounds = len(items) - 1
npairs = len(items) // 2
return [
list(zip(
chain(fixed, islice(cyclers, npairs-1)),
reversed(list(islice(cyclers, npairs)))
))
for _ in range(rounds)
for _ in [next(cyclers)]
]
Ответ 2
Я генерирую только индексы (потому что у меня возникают проблемы с 1000 именами =), но для 1000 номеров время выполнения составляет около 4 секунд.
Основная проблема всех других подходов - они используют пары и работают с ними, есть много пар, и время работы становится намного дольше. Мой подход отличается в работе с людьми, а не с парами. У меня есть dict()
который отображает человека в список других лиц, с которыми он должен встретиться, и эти списки содержат не более N элементов (не N ^ 2, как и пары). Следовательно, экономия времени.
#!/usr/bin/env python
from itertools import combinations
from collections import defaultdict
pairs = combinations( range(6), 2 )
pdict = defaultdict(list)
for p in pairs :
pdict[p[0]].append( p[1] )
while len(pdict) :
busy = set()
print '-----'
for p0 in pdict :
if p0 in busy : continue
for p1 in pdict[p0] :
if p1 in busy : continue
pdict[p0].remove( p1 )
busy.add(p0)
busy.add(p1)
print (p0, p1)
break
# remove empty entries
pdict = { k : v for k,v in pdict.items() if len(v) > 0 }
'''
output:
-----
(0, 1)
(2, 3)
(4, 5)
-----
(0, 2)
(1, 3)
-----
(0, 3)
(1, 2)
-----
(0, 4)
(1, 5)
-----
(0, 5)
(1, 4)
-----
(2, 4)
(3, 5)
-----
(2, 5)
(3, 4)
'''
Ответ 3
Две вещи, которые вы можете сделать сразу с места в карьер:
-
Не делайте копию набора каждый раз через список. Это большая трата времени/памяти. Вместо этого измените набор один раз после каждой итерации.
-
Держите отдельный набор людей в каждом раунде. Поиск человека в наборе будет на порядок быстрее, чем цикл вокруг всего раунда.
Пример:
def make_rounds(people):
people_pairs = set(combinations(people, 2))
while people_pairs:
round = set()
people_covered = set()
for pair in people_pairs:
if pair[0] not in people_covered \
and pair[1] not in people_covered:
round.add(pair)
people_covered.update(pair)
people_pairs -= round # remove thi
yield round
Сравнение:
Ответ 4
Когда вам нужны быстрые поисковые запросы, хеши/дикты - это путь. Следите за тем, кто был в каждом раунде в dict
а не в list
и это будет намного быстрее.
Поскольку вы получаете алгоритмы, изучение большой нотации O поможет вам и знает, какие структуры данных хороши в отношении того, какие операции также являются ключевыми. См. Это руководство: https://wiki.python.org/moin/TimeComplexity для временной сложности встроенных модулей Python. Вы увидите, что проверка элемента в списке - это O (n), что означает, что он линейно масштабируется с размером ваших входов. Итак, поскольку он находится в цикле, вы оказываетесь в O (n ^ 2) или хуже. Для dicts поиск, как правило, O (1) означает, что не имеет значения размер вашего ввода.
Кроме того, не переопределяйте встроенные модули. Я бы изменил round
до round_
from itertools import combinations
# test if person already exists in any pairing inside a round of pairs
def person_in_round(person, people_dict):
return people_dict.get(person, False)
def make_rounds(people):
people_pairs = set(combinations(people, 2))
people_in_round = {}
# 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_ = []
people_dict = {}
# 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], people_dict) and not person_in_round(pair[1], people_dict):
round_.append(pair)
people_dict[pair[0]] = True
people_dict[pair[1]] = True
people_pairs.remove(pair)
yield round_
Ответ 5
Может быть, я что-то упустил (не совсем необычно), но это звучит как простой старый турнир с круговым движением, где каждая команда играет каждую другую команду ровно один раз.
Существуют методы O (n ^ 2) для обработки этого "вручную", которые работают "по машине" просто отлично. Одно хорошее описание можно найти в статье Википедии о турнирах Round-Robin.
О том, что O (n ^ 2): будут n-1 или n раундов, каждый из которых требует O (n) шагов для поворота всех, кроме одной записи таблицы, и шагов O (n) для перечисления совпадений n//2
в каждом круглый. Вы можете сделать поворот O (1), используя двусвязные списки, но перечисление совпадений по-прежнему равно O (n). Таким образом, O (n) * O (n) = O (n ^ 2).
Ответ 6
Это занимает около 45 секунд на моем компьютере
def make_rnds(people):
people_pairs = set(combinations(people, 2))
# we will remove pairings from people_pairs whilst we build rnds, so loop as long as people_pairs is not empty
while people_pairs:
rnd = []
rnd_set = set()
peeps = set(people)
# make a copy of the current state of people_pairs to iterate over safely
for pair in set(people_pairs):
if pair[0] not in rnd_set and pair[1] not in rnd_set:
rnd_set.update(pair)
rnd.append(pair)
peeps.remove(pair[0])
peeps.remove(pair[1])
people_pairs.remove(pair)
if not peeps:
break
yield rnd
Я сбросил функцию person_in_rnd
чтобы сократить время, person_in_rnd
на вызовы функций, и добавил переменную rnd_set и peeps. rnd_set - это набор всех участников раунда и используется для проверки совпадений с парой. peeps - это скопированный набор людей, каждый раз, когда мы добавляем пару в rnd, мы удаляем этих лиц из peeps. Это позволяет нам прекратить повторение всех комбинаций, когда peeps пуст, то есть, как только все будут в раунде.