Python中的组合数学

Question

我有一个简单的树状结构，如下所示：

这里的 p 是父节点，c 是子节点，b 是一些假设的分支。

我想找出所有的组合，但有个限制：每个父节点只能连接到一个子节点，并且两个分支不能共享同一个父节点或子节点。

比如，如果 combo 是组合的集合：

combo[0] = [b[0], b[3]]
combo[1] = [b[0], b[4]]
combo[2] = [b[1], b[4]]
combo[3] = [b[2], b[3]]

我觉得这就是所有的组合了。=)

我想知道如何在 Python 中自动实现这一点，适用于任意数量的父节点、子节点和分支。

补充说明：

这其实不是树，而是一个二分图和有向无环图。

Answer 1

看看这个itertools库里的组合生成器：

• product()：生成所有可能的组合
• permutations()：生成所有可能的排列
• combinations()：生成不重复的组合
• combinations_with_replacement()：生成可以重复的组合

看起来你可以写一个迭代器来实现你想要的功能。

Answer 2

这里有一种方法可以做到这一点。虽然还有很多小的优化可以尝试，但这些优化的效果会根据数据的大小而有所不同。

import collections as co
import itertools as it

def unique(list_):
    return len(set(list_)) == len(list_)

def get_combos(branches):
    by_parent = co.defaultdict(list)

    for branch in branches:
        by_parent[branch.p].append(branch)

    combos = it.product(*by_parent.values())

    return it.ifilter(lambda x: unique([b.c for b in x]), combos)

我很确定这个方法至少达到了最佳的复杂度，因为我看不出有什么办法可以不去查看每一个独特的组合。