Вот довольно эффективный алгоритм. Это нормально для небольших наборов данных, но для больших наборов данных потребуется время и оперативная память. Я не буду утверждать, что это алгоритм best , но он, безусловно, намного лучше, чем проверка методом «грубой силы» каждого хорошего - плохого спаривания.
Ключевым моментом является то, что нам не нужно смотреть на отдельные хорошие - плохие пары, мы можем смотреть на общую хорошую - плохую оценку целых команд. Пусть счет для двух действительных команд будет (X, A) и (Y, B). То есть, X - это общий счет всех хороших игроков в команде 1, а A - это общий результат всех плохих игроков в команде 1. Аналогичным образом, Y - это счет хороших игроков в команде 2, а B - это счет плохие игроки в этой команде. Тогда
X - A = Y - B
X + B = Y + A
2(X + B) = X + B + Y + A
X + B = (X + B + Y + A) / 2
Let M = (X + Y + A + B) / 2
Thus B = M - X
Таким образом, нам просто нужно вычислить M, общее количество очков всех игроков, а затем для каждого раздела хорошего игрока X нам нужно посмотреть, есть ли соответствующий раздел плохого игрока B. (Кстати, приведенная выше арифметика показывает, что X + Y + A + B должно быть четным, чтобы решение существовало, поскольку B & X должны быть целыми числами).
Чтобы сделать это с разумной эффективностью, мы создаем диктат плохих игроков. Ключ dict - это общий балл для этого раздела, соответствующее значение - список всех разделов плохого игрока с таким счетом.
Затем мы перебираем пары разделов хорошего игрока Мы находим общий балл за 1-й раздел в паре, вычитаем его из M, чтобы получить требуемую плохую оценку, и проверяем, есть ли эта плохая оценка в словаре. Если это так, мы нашли решение.
Функция equal_parts - это самый быстрый способ, которым я знаю в чистом Python, разбить список на все его равные по длине разделы, см. этот ответ Я написал пару лет назад для подробностей.
Приведенный ниже код находит единственное решение для данных, приведенных в вопросе; это решение дает 2 варианта для каждой команды. Я включил дополнительный код (в настоящее время закомментированный), чтобы сгенерировать случайные поддельные данные, чтобы проверить код на большом наборе данных.
Обновление
В логике предыдущей версии была небольшая ошибка. Когда я нашел список плохих разделов с правильным общим счетом b1, я использовал bad_total - b1, чтобы получить дополнительный список плохих разделов для другой команды. Но это не всегда работает правильно. : oops: В новой версии используется словарь bad_parts, в котором каждый неверный раздел хранится как ключ и значение, что упрощает получение правильного дополнительного раздела.
Кроме того, старая функция make_pairs была немного неаккуратной, поэтому она могла создавать списки Команды 1 и Команды 2, которые разделяли игроков. : другие упс. Теперь у нас есть новая функция make_teams, которая вызывает восстановленный make_pairs. Функция make_teams печатает различные перестановки Команды 1 и Команды 2 в секциях. В каждом разделе ни один из списков Команды 1 не поделится игроками со списком Команды 2.
Я также внес несколько других незначительных изменений, главное из которых состоит в том, что имена в кортеже разделов всегда сортируются в алфавитном порядке. Это делает их использование в качестве словарных ключей более надежным. Я также немного подправил формат вывода.
Иногда может случиться (например, в Решении 23 данных, которые вы предоставили в комментарии), что предполагаемое Решение не работает: нет перестановки плохих игроков, которые можно объединить с хорошими игроками без получения отрицательного результата. Надеюсь, это не главная проблема. Чтобы код автоматически справлялся с этим, нам нужно изменить его так, чтобы вместо печати результатов по мере необходимости, они сохраняли результаты в списках (или, возможно, использовали генераторы), а затем проверяли, что полученные списки не являются пусто перед печатью этого решения. Это потребовало бы намного больше оперативной памяти и сделало бы логику еще более загроможденной, чем сейчас.
from itertools import combinations, permutations
from collections import defaultdict
from random import seed, randrange
seed(37)
def equal_parts(lst):
''' yield all equal-sized pair partitions of lst '''
first = lst[0]
allset_diff = set(lst).difference
for left in combinations(lst, len(lst) // 2):
if left[0] != first:
break
yield left, tuple(sorted(allset_diff(left)))
def find_partitions(bad, good):
print('bad', bad, len(bad))
print('good', good, len(good))
bad_total = sum(bad.values())
good_total = sum(good.values())
total = bad_total + good_total
if total % 2 != 0:
print('No solutions!')
return
magic = total // 2
print('magic =', magic)
# Create a dict of the good partition pairs
good_parts = dict(equal_parts(sorted(good)))
# Create a dict of the bad partition pairs, with each partition of
# the pair as a key and the complementary partiton as the value
bad_parts = {}
for bpart1, bpart2 in equal_parts(sorted(bad)):
bad_parts[bpart1] = bpart2
bad_parts[bpart2] = bpart1
#print(bad_parts)
# Get the sums of all the bad partitions, and save them in
# a dict of lists with the partition sum as the key and
# the partition in the value list
bad_sums = defaultdict(list)
for bpart in bad_parts:
s = sum(bad[k] for k in bpart)
bad_sums[s].append(bpart)
bad_sums = dict(bad_sums)
#print(bad_sums)
# Sum the 1st of each pair of good partitions & see if there's a matching bad partition
count = 0
for gpart1, gpart2 in good_parts.items():
g1 = sum(good[k] for k in gpart1)
b1 = magic - g1
if b1 in bad_sums:
count += 1
print('SOLUTION', count)
g2 = good_total - g1
b2 = bad_total - b1
blist1 = bad_sums[b1]
# Create the complementary list of bad partitions
blist2 = [bad_parts[k] for k in blist1]
tot1 = g1 - b2
tot2 = g2 - b1
print(gpart1, g1, '-', blist2, b2, '=', tot1)
print(gpart2, g2, '-', blist1, b1, '=', tot2, '\n')
make_teams(gpart1, gpart2, blist1, blist2)
def make_pairs(gpart, bpart):
for b in permutations(bpart):
total = 0
team = []
for gkey, bkey in zip(gpart, b):
score = good[gkey] - bad[bkey]
if score <= 0:
# Invalid pairing
break
total += score
team.append('{}-{}={}'.format(gkey, bkey, score))
else:
print(', '.join(team), total)
def make_teams(gpart1, gpart2, blist1, blist2):
section = 0
for bpart2, bpart1 in zip(blist2, blist1):
section += 1
print('Section', section)
print('Team 1:', ' '.join(gpart1), '+', ' '.join(bpart2))
make_pairs(gpart1, bpart2)
print('\nTeam 2:', ' '.join(gpart2), '+', ' '.join(bpart1))
make_pairs(gpart2, bpart1)
print()
# Make some fake data
def make_data(letters, lo, hi):
return {s: randrange(lo, hi) for s in letters}
#while True:
#bad = make_data('ZYXWVU', 1, 15)
#good = make_data('ABCDEF', 10, 30)
#bad_total = sum(bad.values())
#good_total = sum(good.values())
#if bad_total % 2 == good_total % 2:
#break
bad = {'A': 13, 'B': 6, 'C': 9, 'D': 2,}
good = {'X': 25, 'Y': 16, 'Z': 17, 'K': 10,}
#bad = {'bA': 7, 'bB': 10, 'bC': 2, 'bD': 12, 'bE': 15, 'bF': 14, 'bG': 17, 'bH': 15}
#good = {'gA': 19, 'gB': 36, 'gC': 9, 'gD': 15, 'gE': 24, 'gF': 23, 'gG': 24, 'gH': 24}
find_partitions(bad, good)
выход
bad {'A': 13, 'B': 6, 'C': 9, 'D': 2} 4
good {'X': 25, 'Y': 16, 'Z': 17, 'K': 10} 4
magic = 49
SOLUTION 1
('K', 'Z') 27 - [('B', 'D')] 8 = 19
('X', 'Y') 41 - [('A', 'C')] 22 = 19
Section 1
Team 1: K Z + B D
K-B=4, Z-D=15 19
K-D=8, Z-B=11 19
Team 2: X Y + A C
X-A=12, Y-C=7 19
X-C=16, Y-A=3 19
Вот вывод из фальшивых данных.
bad {'Z': 2, 'Y': 9, 'X': 5, 'W': 6, 'V': 11, 'U': 12} 6
good {'A': 23, 'B': 28, 'C': 28, 'D': 21, 'E': 28, 'F': 11} 6
magic = 92
SOLUTION 1
('A', 'B', 'C') 79 - [('U', 'V', 'Y')] 32 = 47
('D', 'E', 'F') 60 - [('W', 'X', 'Z')] 13 = 47
Section 1
Team 1: A B C + U V Y
A-U=11, B-V=17, C-Y=19 47
A-U=11, B-Y=19, C-V=17 47
A-V=12, B-U=16, C-Y=19 47
A-V=12, B-Y=19, C-U=16 47
A-Y=14, B-U=16, C-V=17 47
A-Y=14, B-V=17, C-U=16 47
Team 2: D E F + W X Z
D-W=15, E-X=23, F-Z=9 47
D-W=15, E-Z=26, F-X=6 47
D-X=16, E-W=22, F-Z=9 47
D-X=16, E-Z=26, F-W=5 47
D-Z=19, E-W=22, F-X=6 47
D-Z=19, E-X=23, F-W=5 47
SOLUTION 2
('A', 'B', 'D') 72 - [('U', 'V', 'Z'), ('V', 'X', 'Y')] 25 = 47
('C', 'E', 'F') 67 - [('W', 'X', 'Y'), ('U', 'W', 'Z')] 20 = 47
Section 1
Team 1: A B D + U V Z
A-U=11, B-V=17, D-Z=19 47
A-U=11, B-Z=26, D-V=10 47
A-V=12, B-U=16, D-Z=19 47
A-V=12, B-Z=26, D-U=9 47
A-Z=21, B-U=16, D-V=10 47
A-Z=21, B-V=17, D-U=9 47
Team 2: C E F + W X Y
C-W=22, E-X=23, F-Y=2 47
C-W=22, E-Y=19, F-X=6 47
C-X=23, E-W=22, F-Y=2 47
C-X=23, E-Y=19, F-W=5 47
C-Y=19, E-W=22, F-X=6 47
C-Y=19, E-X=23, F-W=5 47
Section 2
Team 1: A B D + V X Y
A-V=12, B-X=23, D-Y=12 47
A-V=12, B-Y=19, D-X=16 47
A-X=18, B-V=17, D-Y=12 47
A-X=18, B-Y=19, D-V=10 47
A-Y=14, B-V=17, D-X=16 47
A-Y=14, B-X=23, D-V=10 47
Team 2: C E F + U W Z
C-U=16, E-W=22, F-Z=9 47
C-U=16, E-Z=26, F-W=5 47
C-W=22, E-U=16, F-Z=9 47
C-Z=26, E-U=16, F-W=5 47
SOLUTION 3
('A', 'B', 'E') 79 - [('U', 'V', 'Y')] 32 = 47
('C', 'D', 'F') 60 - [('W', 'X', 'Z')] 13 = 47
Section 1
Team 1: A B E + U V Y
A-U=11, B-V=17, E-Y=19 47
A-U=11, B-Y=19, E-V=17 47
A-V=12, B-U=16, E-Y=19 47
A-V=12, B-Y=19, E-U=16 47
A-Y=14, B-U=16, E-V=17 47
A-Y=14, B-V=17, E-U=16 47
Team 2: C D F + W X Z
C-W=22, D-X=16, F-Z=9 47
C-W=22, D-Z=19, F-X=6 47
C-X=23, D-W=15, F-Z=9 47
C-X=23, D-Z=19, F-W=5 47
C-Z=26, D-W=15, F-X=6 47
C-Z=26, D-X=16, F-W=5 47
SOLUTION 4
('A', 'C', 'D') 72 - [('U', 'V', 'Z'), ('V', 'X', 'Y')] 25 = 47
('B', 'E', 'F') 67 - [('W', 'X', 'Y'), ('U', 'W', 'Z')] 20 = 47
Section 1
Team 1: A C D + U V Z
A-U=11, C-V=17, D-Z=19 47
A-U=11, C-Z=26, D-V=10 47
A-V=12, C-U=16, D-Z=19 47
A-V=12, C-Z=26, D-U=9 47
A-Z=21, C-U=16, D-V=10 47
A-Z=21, C-V=17, D-U=9 47
Team 2: B E F + W X Y
B-W=22, E-X=23, F-Y=2 47
B-W=22, E-Y=19, F-X=6 47
B-X=23, E-W=22, F-Y=2 47
B-X=23, E-Y=19, F-W=5 47
B-Y=19, E-W=22, F-X=6 47
B-Y=19, E-X=23, F-W=5 47
Section 2
Team 1: A C D + V X Y
A-V=12, C-X=23, D-Y=12 47
A-V=12, C-Y=19, D-X=16 47
A-X=18, C-V=17, D-Y=12 47
A-X=18, C-Y=19, D-V=10 47
A-Y=14, C-V=17, D-X=16 47
A-Y=14, C-X=23, D-V=10 47
Team 2: B E F + U W Z
B-U=16, E-W=22, F-Z=9 47
B-U=16, E-Z=26, F-W=5 47
B-W=22, E-U=16, F-Z=9 47
B-Z=26, E-U=16, F-W=5 47
SOLUTION 5
('A', 'C', 'E') 79 - [('U', 'V', 'Y')] 32 = 47
('B', 'D', 'F') 60 - [('W', 'X', 'Z')] 13 = 47
Section 1
Team 1: A C E + U V Y
A-U=11, C-V=17, E-Y=19 47
A-U=11, C-Y=19, E-V=17 47
A-V=12, C-U=16, E-Y=19 47
A-V=12, C-Y=19, E-U=16 47
A-Y=14, C-U=16, E-V=17 47
A-Y=14, C-V=17, E-U=16 47
Team 2: B D F + W X Z
B-W=22, D-X=16, F-Z=9 47
B-W=22, D-Z=19, F-X=6 47
B-X=23, D-W=15, F-Z=9 47
B-X=23, D-Z=19, F-W=5 47
B-Z=26, D-W=15, F-X=6 47
B-Z=26, D-X=16, F-W=5 47
SOLUTION 6
('A', 'D', 'E') 72 - [('U', 'V', 'Z'), ('V', 'X', 'Y')] 25 = 47
('B', 'C', 'F') 67 - [('W', 'X', 'Y'), ('U', 'W', 'Z')] 20 = 47
Section 1
Team 1: A D E + U V Z
A-U=11, D-V=10, E-Z=26 47
A-U=11, D-Z=19, E-V=17 47
A-V=12, D-U=9, E-Z=26 47
A-V=12, D-Z=19, E-U=16 47
A-Z=21, D-U=9, E-V=17 47
A-Z=21, D-V=10, E-U=16 47
Team 2: B C F + W X Y
B-W=22, C-X=23, F-Y=2 47
B-W=22, C-Y=19, F-X=6 47
B-X=23, C-W=22, F-Y=2 47
B-X=23, C-Y=19, F-W=5 47
B-Y=19, C-W=22, F-X=6 47
B-Y=19, C-X=23, F-W=5 47
Section 2
Team 1: A D E + V X Y
A-V=12, D-X=16, E-Y=19 47
A-V=12, D-Y=12, E-X=23 47
A-X=18, D-V=10, E-Y=19 47
A-X=18, D-Y=12, E-V=17 47
A-Y=14, D-V=10, E-X=23 47
A-Y=14, D-X=16, E-V=17 47
Team 2: B C F + U W Z
B-U=16, C-W=22, F-Z=9 47
B-U=16, C-Z=26, F-W=5 47
B-W=22, C-U=16, F-Z=9 47
B-Z=26, C-U=16, F-W=5 47
PS. Я подумал о способе быстрой обработки намного больших наборов данных. Он не найдет всех решений, но он должен найти их множество. Идея состоит в том, чтобы разделить большой набор данных на несколько меньших наборов, решить эти меньшие наборы независимо, а затем объединить решения. Единственная сложная задача - выполнить деление так, чтобы каждый меньший набор был разрешимым. Так в каждом наборе bad_total < good_total и bad_total%2 == good_total%2. Вероятно, имеет смысл отсортировать полные наборы данных по количеству баллов, прежде чем пытаться разделить их так, чтобы плохие и хорошие группы каждого меньшего набора были приблизительно сопоставлены.