我有一种一级树结构:
其中p是父节点,c是子节点,b是假设分支.
我想在约束条件下找到所有分支组合,只有一个父级只能分支到一个子节点,而两个分支不能共享父级和/或子级.
例如.如果组合是一组组合:
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)
我很确定这至少会达到最佳复杂性,因为我没有办法避免查看父母所独有的每个组合.