Найти наиболее эффективные группы пар

Ответ 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

Две вещи, которые вы можете сделать сразу с места в карьер:

1. Не делайте копию набора каждый раз через список. Это большая трата времени/памяти. Вместо этого измените набор один раз после каждой итерации.

2. Держите отдельный набор людей в каждом раунде. Поиск человека в наборе будет на порядок быстрее, чем цикл вокруг всего раунда.

Пример:

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 пуст, то есть, как только все будут в раунде.