Python Combinatorics,第2部分

Question

这是Python中Combinatorics的后续问题

如果您将使用以下结构,我有一棵树或有向无环图:

其中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)

...这正是您想要的。

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

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