生成每个组合的列表，不重复

Question

我想生成一个组合列表。我会尽力简化我的问题以使其易于理解。

我们有 3 个变量：

• x : 字母数量
• k : 组数
• n ：每组的字母数

我想使用 python 生成每个可能组合的列表，没有任何重复知道：我不关心组的顺序和组内字母的顺序。

例如，当 x = 4、k = 2、n = 2 时：

# we start with 4 letters, we want to make 2 groups of 2 letters
letters = ['A','B','C','D']

# here would be a code that generate the list

# Here is the result that is very simple, only 3 combinations exist.
combos = [ ['AB', 'CD'], ['AC', 'BD'], ['AD', 'BC'] ]

因为我不关心组内或组内的顺序，以及组内的字母，['AB', 'CD']并且['DC', 'BA']是重复的。

这是我的实际问题的简化，它具有这些值：x = 12，，，k = 4。n = 3我尝试使用 中的一些功能itertools，但由于字母太多，我的计算机冻结了，因为组合太多。

另一种看待问题的方式：你有 12 名球员，你想组成 4 支球队，每队 3 名球员。所有的可能性是什么？

谁能帮我找到一个优化的解决方案来生成这个列表？

Answer 1

当然会有更复杂/更有效的方法来做到这一点，但这里有一种方法可以在合理的时间内为您的示例工作，并且应该足够容易适应其他情况。

它根据您的规格生成独特的团队及其独特的组合。

from itertools import combinations

# this assumes that team_size * team_num == len(players) is a given
team_size = 3
team_num = 4
players = list('ABCDEFGHIJKL')
unique_teams = [set(c) for c in combinations(players, team_size)]

def duplicate_player(combo):
    """Returns True if a player occurs in more than one team"""
    return len(set.union(*combo)) < len(players)
    
result = (combo for combo in combinations(unique_teams, team_num) if not duplicate_player(combo))

result是一个可以迭代或转换为列表的生成器list(result)。在 kaggle.com 上，需要一分钟左右的时间才能生成所有可能组合的完整列表（总共 15400 个，与评论中 @beaker 和 @John Coleman 的计算一致）。团队是如下所示的集合元组：

[({'A', 'B', 'C'}, {'D', 'E', 'F'}, {'G', 'H', 'I'}, {'J', 'K', 'L'}),
 ({'A', 'B', 'C'}, {'D', 'E', 'F'}, {'G', 'H', 'J'}, {'I', 'K', 'L'}),
 ({'A', 'B', 'C'}, {'D', 'E', 'F'}, {'G', 'H', 'K'}, {'I', 'J', 'L'}),
 ...
]

如果需要，您可以通过调用''.join()每个字符串将它们转换为字符串。