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中，对于这种结构的任意树（即p:s、c:s和b:s的数目是任意的），如何自动实现这一点。

编辑：

它不是一棵树，而是一棵bipartitedirected acyclic graph

Answer 1

看看itertools组合生成器：

• 产品（）
• 置换（）
• 组合（）
• 带替换的组合（）

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

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)

我很确定这至少达到了最佳的复杂度，因为我看不出有什么方法可以避免看到父级所特有的每个组合。