这是对Python中组合数学问题的跟进问题。
我有一棵树或有向无环图，其结构如下：
其中r是根节点，p是父节点，c是子节点，b是假想分支。根节点与父节点没有直接链接，仅为引用。
我希望在以下约束条件下找到所有分支的组合：
在此示例中，只有两个符合约束条件的组合是可能的：
combo[0] = [b[0], b[1], b[2], b[3]]
combo[1] = [b[0], b[1], b[2], b[4]]
b[3].r = 1
b[3].p = 3
b[3].c = 2
class HypotheticalBranch(object):
def __init__(self, r, p, c):
self.r=r
self.p=p
self.c=c
def __repr__(self):
return "HypotheticalBranch(%d,%d,%d)" % (self.r,self.p,self.c)
b=[ HypotheticalBranch(0,0,0),
HypotheticalBranch(0,1,1),
HypotheticalBranch(1,2,1),
HypotheticalBranch(1,3,2),
HypotheticalBranch(1,4,2) ]
import collections, itertools
def get_combos(branches):
rc=collections.defaultdict(list)
for b in branches:
rc[b.r,b.c].append(b)
return itertools.product(*rc.values())
准确来说，这个函数返回一个迭代器。通过迭代它来获取列表。以下四行代码将打印出所有可能的组合：
for combo in get_combos(b):
print "Combo:"
for branch in combo:
print " %r" % (branch,)
Combo:
HypotheticalBranch(0,1,1)
HypotheticalBranch(1,3,2)
HypotheticalBranch(0,0,0)
HypotheticalBranch(1,2,1)
Combo:
HypotheticalBranch(0,1,1)
HypotheticalBranch(1,4,2)
HypotheticalBranch(0,0,0)
HypotheticalBranch(1,2,1)
...这正是你想要的。
那么这个脚本是做什么的呢？它为每个组合（根节点、子节点）创建了所有假设分支的列表。然后，它产生这些列表的乘积，即所有可能的每个列表中的一个项目的组合。
我希望我理解了你真正想要的内容。
你的第二个限制意味着你想要最大化组合，即所有长度等于最大组合长度的组合。
我会先遍历“b”结构并创建一个名为“c”的结构来存储到达每个子节点的所有分支，并按其根节点进行分类。
然后为了构建输出的组合，对于每个子节点，您可以包含不为空的每个根集中的一个条目。算法的顺序（执行时间）将是输出的顺序，这是您可以获得的最佳顺序。
例如，您的“c”结构将如下所示：
c[i][j] = [b_k0, ...]
--> means c_i has b_k0, ... as branches that connect to root r_j)
针对您提供的示例：
c[0][0] = [0]
c[0][1] = []
c[1][0] = [1]
c[1][1] = [2]
c[2][0] = []
c[2][1] = [3, 4]
使用这种方法编写代码应该相当容易。只需迭代所有分支“b”，并为“c”填充数据结构。然后编写一个小的递归函数，遍历“c”中的所有项。
这是代码（我在顶部输入了您的样本数据以进行测试）：
class Branch:
def __init__(self, r, p, c):
self.r = r
self.p = p
self.c = c
b = [
Branch(0, 0, 0),
Branch(0, 1, 1),
Branch(1, 2, 1),
Branch(1, 3, 2),
Branch(1, 4, 2)
]
total_b = 5 # Number of branches
total_c = 3 # Number of child nodes
total_r = 2 # Number of roots
c = []
for i in range(total_c):
c.append([])
for j in range(total_r):
c[i].append([])
for k in range(total_b):
c[b[k].c][b[k].r].append(k)
combos = []
def list_combos(n_c, n_r, curr):
if n_c == total_c:
combos.append(curr)
elif n_r == total_r:
list_combos(n_c+1, 0, curr)
elif c[n_c][n_r]:
for k in c[n_c][n_r]:
list_combos(n_c, n_r+1, curr + [b[k]])
else:
list_combos(n_c, n_r+1, curr)
list_combos(0, 0, [])
print combos
这里实际上有两个问题：首先，你需要想出一个算法来解决这个问题；其次，你需要在 Python 中实现它。
我假设您想要一个最大的分支集合；也就是说，您不能再添加任何分支。如果不需要，则可以考虑最大集合的所有子集。
因此，对于子节点，我们希望尽可能多地采用分支，但又不能让两个父节点共享根节点。换句话说，从每个子节点到每个根节点的邻域中，您最多只能有一条边。这似乎表明您希望首先迭代子节点，然后迭代（邻域的）根节点，最后迭代它们之间的边缘。这个概念给出了以下伪代码：
for each child node:
for each root node:
remember each permissible edge
find all combinations of permissible edges
>>> import networkx as nx
>>> import itertools
>>>
>>> G = nx.DiGraph()
>>> G.add_nodes_from(["r0", "r1", "p0", "p1", "p2", "p3", "p4", "c0", "c1", "c2"])
>>> G.add_edges_from([("r0", "p0"), ("r0", "p1"), ("r1", "p2"), ("r1", "p3"),
... ("r1", "p4"), ("p0", "c0"), ("p1", "c1"), ("p2", "c1"),
... ("p3", "c2"), ("p4", "c2")])
>>>
>>> combs = set()
>>> leaves = [node for node in G if not G.out_degree(node)]
>>> roots = [node for node in G if not G.in_degree(node)]
>>> for leaf in leaves:
... for root in roots:
... possibilities = tuple(edge for edge in G.in_edges_iter(leaf)
... if G.has_edge(root, edge[0]))
... if possibilities: combs.add(possibilities)
...
>>> combs
set([(('p1', 'c1'),),
(('p2', 'c1'),),
(('p3', 'c2'), ('p4', 'c2')),
(('p0', 'c0'),)])
>>> print list(itertools.product(*combs))
[(('p1', 'c1'), ('p2', 'c1'), ('p3', 'c2'), ('p0', 'c0')),
(('p1', 'c1'), ('p2', 'c1'), ('p4', 'c2'), ('p0', 'c0'))]
上述代码看起来应该是可行的，尽管我还没有测试过。