高效组合与条件

Question

给定代表玩家数量的用户输入n，我计算玩家的所有可能联盟（元组），然后计算所有可能的联盟集合，以便在每个集合中每个玩家都属于一个且仅属于一个联盟。 示例：n = 3

#coalitions
[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

#combinations of coalitions that respect the condition
[((1, 2, 3),), ((1,), (2, 3)), ((2,), (1, 3)), ((3,), (1, 2)), ((1,), (2,), (3,))]

为了做到这一点，我写道：

^{pr2}$

问题是coal_comb效率极低。对于距离，它将计算长度n的所有组合，即使只有一个（即((1 ... n),)）符合条件。在

我认为函数是O（2^（2^n））。 我的电脑甚至不能计算n=6。在

有什么办法让它更有效率吗？在

更新 我想出了一个解决方案：

combs = [comb for length in xrange(2,n) for comb in combinations_with_replacement(players,length) if sum(comb) == n]
H = [tuple(players_comb[:n]),(players_comb[-1],)]
for comb in combs:
    layouts = set(frozenset(layout) for layout in product(*[[coal for coal in players_comb if len(coal) == length] for length in comb]) if set(player for coal in layout for player in coal) == set(players))
    H.extend(tuple(tuple(layout) for layout in layouts))

但这只是一个小小的改进：现在我可以计算n = 8（运行时间超过50秒）。在