python - 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 的数量是任意的。

编辑：

它不是一棵树，而是一个二部有 向无环图

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)

我很确定这至少达到了最佳复杂性，因为我没有看到避免查看父母唯一的每个组合的方法。

Answer 2

看看itertools组合生成器：

• 产品（）
• 排列（）
• 组合（）
• combination_with_replacement()

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