python - Python 中的组合学

Question

我有一种单层树结构:

其中 p 是父节点，c 是子节点，b 是假设分支。

我想在只有一个父节点可以分支到只有一个子节点和两个分支的约束下找到分支的所有组合不能共享 parent 和/或 child 。

例如如果 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

Answer 1

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

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)

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