python - 在保持平衡的同时将不良球员与优秀球员配对

Question

我有很多球员分成两组，好球员和坏球员每个播放器由一个算术值定义，可能的组可以是这个：

bad players
A 13
B 6
C 9
D 2

good players
X 25
Y 16
Z 17
K 10

把一个好的玩家和一个坏的玩家配对会使他变得更糟，其数量等于坏玩家的价值（因此，如果我把一个值为100的好玩家和一个值为50的坏玩家配对，那么好玩家的价值就会下降到50）我需要把每一个好的玩家和一个坏的玩家配对，但是这样一来，结果列表中好的玩家的总和就可以被分成两个大小相等、总和相同的组。
在我上面的例子中，一个糟糕的配对应该是：

A - X 12
C - Z 8
B - Y 10
D - K 8

现在，由于他们与坏球员（a b c d）的配对，所有的好球员都失去了一些积分，他们的价值也发生了变化。这些新值不能分成大小相等的两组，因为每组中的值之和相等。如果我有一个不同的组合，让我们说：

D - K 8
B - Z 11
C - X 16
A - Y 3 

我现在可以把优秀的球员分成K，Z和X，Y三组，它们的值都是19，所以一切保持中立。
为了找到一个好的和坏的玩家可以接受的配对，一个解决方案是使用暴力并产生所有可能的组合，并通过尝试将每个组合分成两个等价的组来检查是否可以接受一旦找到第一个可接受的解决方案，我们就将其退回。
如何改进此设置并直接在此设置中找到可接受的配对？

Answer 1

这是一个相当有效的算法对于小数据集是可以的，但是对于大数据集则需要时间和RAM我不会说这是最好的算法，但它肯定比暴力检查每一个好的-坏的配对要好得多。
关键的见解是，我们不需要看个人的好坏配对，我们可以看整个球队的总的好坏得分。让两个有效团队的得分为（x，a）和（y，b）。也就是说，X是一队所有优秀球员的总分，A是一队所有不良球员的总分同样，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。dict键是该分区的总分，关联的值是具有该分数的所有坏播放器分区的列表。
然后我们循环好的播放器分区对。我们找到一对中第一个分区的总分，从M中减去它，得到所需的坏分数，然后看看这个坏分数是否在字典中如果是的话，我们找到了解决办法。
在纯python中，equal_parts函数是我所知道的将一个列表拆分为所有等长分区的最快方法，有关详细信息，请参见我几年前编写的this answer。
下面的代码为问题中给定的数据找到一个单一的解决方案；该解决方案为每个团队生成两个选项。为了在更大的数据集上测试代码，我添加了一些额外的代码（目前已经注释掉了）来生成一些随机的伪数据。
更新
上一版本的逻辑中有一个小错误。当我找到一个总得分b1正确的坏分区列表时，我使用bad_total - b1来获取另一个团队的坏分区补充列表。但这并不总是正确的。：oops：新版本使用一个bad_parts字典，它将每个坏分区存储为一个键和一个值，这样就很容易得到正确的互补分区。
另外，旧的make_pairs函数有点草率，因此它可以生成共享玩家的team 1列表和team 2列表。：其他oops:。我们现在有了一个新函数make_teams，它调用已修复的make_pairsmake_teams函数按部分打印各种team 1和team 2排列。在每个部分中，没有一个一队名单将与一个二队名单共享球员。
我还做了一些其他的小改动，主要的改动是分区元组中的名称总是按字母顺序排序的。这使得它们作为字典键的使用更加健壮我还对输出格式做了一些调整。
有时可能会发生（比如在你在评论中提供的数据的解决方案23中）所谓的解决方案不起作用：没有坏玩家的排列可以与好玩家组合而不产生负分数。希望这不是什么大问题。为了使代码能够自动处理这个问题，我们需要更改它，这样它就不必按原样打印结果，而是需要将结果存储在列表中（或者可能使用生成器），然后在打印解决方案之前测试结果列表是否为空这将消耗更多的ram，使逻辑比现在更加混乱。

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   

另外，我想了一种快速处理更大数据集的方法。它不会找到所有的解决方案，但它应该找到很多。其思想是将大数据集分解成若干个小数据集，独立求解这些小数据集，然后组合求解。唯一棘手的部分是进行除法，以便每个较小的集合都是可解的。所以在每一组中bad_total < good_total和bad_total%2 == good_total%2。在尝试划分之前，按分数对完整的数据集进行排序可能是有意义的，这样每个较小的数据集的坏组和好组就可以大致匹配。