Python 组合数学，第二部分

Question

这是一个关于Python中的组合数学的后续问题。

我有一个树形结构或者说是有向无环图，结构如下：

在这个结构中，r代表根节点，p代表父节点，c代表子节点，b代表一些假设的分支。根节点和父节点之间并不是直接相连的，根节点只是一个参考。

我想找到所有在以下约束条件下的分支组合：

1. 一个子节点可以被多个父节点共享，只要这些父节点不共享同一个根节点。
2. 一个有效的组合不能是另一个组合的子集。

在这个例子中，只有两个有效的组合符合这些约束条件：

combo[0] = [b[0], b[1], b[2], b[3]]
combo[1] = [b[0], b[1], b[2], b[4]]

数据结构是这样的，b是一个分支对象的列表，这些对象有属性r、c和p，例如：

b[3].r = 1
b[3].p = 3
b[3].c = 2

Answer 1

这里其实有两个问题：首先，你需要想出一个算法来解决这个问题，其次，你需要用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'))]

上面的代码看起来是可行的，虽然我还没有测试过。

Answer 2

你的第二个限制条件意味着你想要得到最大的组合，也就是所有长度等于最大组合的组合。

我会先遍历“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

Answer 3

这个问题在Python中可以很简单又优雅地解决，因为有一个叫“itertools”的模块。

假设我们有一些叫做HypotheticalBranch的对象，它们有属性r、p和c。就像你在帖子中描述的那样：

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)

...正是你想要的结果。

那么这个脚本到底做了什么呢？它为每种组合（根节点、子节点）创建了一组所有假设分支。然后它生成这些列表的乘积，也就是从每个列表中选一个项目的所有可能组合。

希望我理解了你真正想要的。