Python 组合数学，第 2 部分

Question

这是 Combinatorics in 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 中可以轻松优雅地解决，因为有一个名为“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)

...这正是您想要的。

那么脚本是做什么的呢？它为每个组合(根节点、子节点)创建一个所有假设分支的列表。然后它会生成这些列表的乘积，即每个列表中一项的所有可能组合。

我希望我得到了你真正想要的。