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 组合发生器：

• 产品（）
• 排列（）
• 组合（）
• combinations_with_replacement（）

看起来您可以编写一个迭代器来实现所需的目标。