大型数据集和寻找匹配各种标准的排列

Question

我有一个长度为15000的足球运动员列表，它由字典组成(大小相同)。列表中的元素看起来像这样:

{
'id': '123456',
'name': 'Foo Bar',
'position': 'GK',
'club':  'Python FC',
'league': 'Champions League',
'country': 'Neverland'
}

给定一个由11名球员组成的球队，其中每个位置都指定并且必须填补。一个队形可能是这样的:

formation = [('ST', 2), ('LM', 1), ('RM', 1), ('CM', 2), ('LB', 1), ('RB', 1), ('CB', 2), ('GK', 1)]

我想找到符合以下条件的所有可能的球员组合/排列:

形成

• 来自至少5个不同国家的玩家
• 同一俱乐部最多4个

What I have try

假设my_list是所有玩家的列表;

尝试1

from itertools import *
squads = permutations(my_list,11)
match_countries = [squad for squad in squads if 
Counter([player['country'] for player in squad]).most_common().__len__() >= 5
and Counter([player['club'] for player in squad]).most_common().__len__() <= 4
]  

但这将花费太长时间，因为我有一个错误的小队。

尝试2我仍然使用最初相同的球员列表，将其分成每个位置列表。所以我有一个每个位置的球员列表，像这样:

list_goalkeepers = [player for player in my_list if player['position'] == 'GK']

然后用这些列表组成小队。例如，一个有两名前锋和一名门将的阵容是这样的:

squads = product(list_goalkeepers, list_strikers, list_strikers, .....)

这仍然导致大量的小队，但至少他们都是有效的;当我尝试查找匹配的国家数量时，它仍然会遍历所有的球队以检查是否存在匹配。我像这样执行国家搜索:

match_countries = [squad for squad in collection 
if Counter([player['country'] for player in squad]).most_common().__len__() >= 5 ]

有什么方法可以快速完成这个?这实在是太慢了。

Answer 1

这里有几件事会有所帮助，但它们不会把这个问题减少到一个可处理的问题(见下文)。

,

squads = product(list_goalkeepers, list_strikers, list_strikers, .....)

实际上不正确。product([striker1, striker2], [striker1, striker2])(只看产品的一小部分)产生四种可能性:

[striker1, striker1]
[striker1, striker2]
[striker2, striker1]
[striker2, striker2]

其中，两个是不正确的，因为同一个球员在一个球队中出现了两次，另外两个是重复的，因为每个球队中球员的顺序是不相关的。所以实际上只有一种合法的组合，{striker1, striker2}。要得到它，你需要itertools.combinations(strikers, 2)。

如果列表A有n元素，product(A, A)将生成n²列表，而combinations(A, 2)将生成(n²-n)/2列表，大约是数量的一半。因为你有三个位置，两个球员，你的product调用产生了超过8倍的小队。所以把它做好会让事情快很多。但这并不像向combination添加一些调用那么简单。你需要做的是像这样:

from collections import defaultdict
from itertools import product, combinations, chain

position_players = defaultdict(list)
for player in all_players:
position_players[player['position']].append(player)
def flatten(list_of_lists):
return [*chain.from_iterable(list_of_lists)]
# See below for more general solution
candidates = [*map(flatten,
product(
product(*(position_players[pos]
for pos in ('LM', 'RM', 'LB', 'RB', 'GK'))),
*(combinations(position_players[pos], 2)
for pos in ('ST', 'CM', 'CB'))))]

一个更通用的解决方案是使用formations来构建最终产品，但我认为上面已经足够难读了:-)。不管怎样，

candidates = [*map(flatten,
product(
*(combinations(position_players[posn], count)
for posn, count in formation)))]

其次，你似乎在执行其他两个标准，每个俱乐部的最大球员数量和最少国家数量，使用涉及counter.most_common().__len__()的相同公式。先不考虑为什么直接调用__len__dunder而不是使用更自然的len(counter.most_common())，这个公式要么不正确，要么效率低下:

• Counter([player['club'] for player in squad]).most_common().__len__() <= 4检查是否有最多四个俱乐部代表在阵容中。但你的标准是任何俱乐部都不能有超过四名球员代表，这将是Counter([player['club'] for player in squad]).most_common(1) <= 4.

• Counter([player['country'] for player in squad]).most_common().__len__() >= 5检查至少有五个国家的代表。但更简单(也更快)的方法也是如此:len(set(player['country'] for player in squad)) >= 5

修复这些将使列表正确，并大大加快解决方案。但这不会真的有帮助。

与许多组合问题一样，很容易低估可能的候选者的数量，从而制定完全不切实际的解决方案，包括生成所有可能性。

作为一个快速的例子，让我们假设5001名球员大致按比例分布在不同的位置上:5个单一位置("LM"，"RM"，"LB"，"RB"，"GK")中的每个位置有1364名候选人，剩下的三个双位置("ST"，"CM"，"CB")中的每个位置有2727名候选人。然后有1364 *(2727 * 2726/2)³个可能的阵容，不考虑国家/俱乐部的标准，这可能不会排除大多数可能性。总共有901,147,384,847,503,556,419,043,700,514,410,951,988,224个可能的小队。我认为可以肯定地说，遍历所有这些并不只是"慢得令人痛苦"。这是不可能在你的一生中(或者，实际上，在地球的预期寿命中)做到的。

你可能最好找到一种方法来创建和使用一个可处理的大小的随机样本，从宇宙的可能性中均匀选择。