python - Python中的组合学

我有一种单层树结构，如下所示:

其中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的数目是任意的。

编辑:

它不是一棵树，而是一棵bipartite directed acyclic graph

最佳答案

这是一种方法。可以进行很多微优化，但是它们的功效取决于所涉及的大小。

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)

我很确定这至少会达到最佳的复杂度，因为我没有找到一种避免查看父项唯一的每种组合的方法。

关于python - Python中的组合学，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4095749/