我有一种单层树结构:
其中 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
最佳答案
这是一种方法。可以进行很多微优化,但它们的效果取决于所涉及的大小。
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/