Python生成符合条件的大集合组合的最有效方法？

Question

我试图在一个受边界条件约束的投资组合中生成所有可能的金融工具组合。在

例如，假设我有一组列表，这些列表表示对投资组合的分配，每个工具的投资组合总规模的最小和最大百分比是：

"US Bonds" = {0.10,0.15,0.20,0.25,0.30}
"US Equities" = {0.25, 0.30, 0.35, 0.40, 0.45, 0.50}
"European Bonds" = {0.10, 0.15, 0.20}
"European Equities = {0.20,0.25,0.30,0.35,0.40,0.45,0.50}
 ...
"Cash" = {0.0, 0.05, 0.10, 0.15,...0.95}

因此，我的列表中的资产如下所示：

^{pr2}$

在所有组合工具之和必须等于1的条件下，生成所有可能投资组合的最有效方法是什么？在

目前，我正在创建一个列表“公文包”，如下所示：

portfolios  = [item for item in itertools.product(*asset) if  np.isclose(sum(item),1)]

（注，'np.isclose公司'来处理时髦的fp算术）。在

我已经将资产类和可能的分配表示为一个列表集合，但不知道是否有一个不同的数据表示（例如，NumPY数组）会更快。在

有一些关于各种组合的最佳执行的问题，但我没有看到任何带有任何边界条件的问题。在

Answer 1

（注意：代码可从：http://lpaste.net/145213获得）

首先，我将百分数表示为整数值，以避免浮点舍入错误。在

其次，最有效的方法是使用边界来避免寻找不可能满足==1约束的投资组合。在

要编写的循环将按如下方式运行：

def portfolios():
  for us_bonds in [ 10, 15, 20, 25, 30 ]:
    if us_bonds > 100: break
    for us_equaties in [ 25, 30, 35, 40, 45, 50 ]:
      if us_bonds + us_equaties > 100: break
      for euro_bonds in [ 10, 15, 20 ]:
        if us_bonds + us_equaties + euro_bonds > 100: break
        for euro_equaties in [ 20, 25, 30, 35, 40, 45, 50 ]:
          if us_bonds + us_equaties + euro_bonds + euro_equaties > 100: break
          cash = 100 - (us_bonds + us_equaties + euro_bonds + euro_equaties)
          yield [us_bonds, us_equaties, euro_bonds, euro_equaties, cash]

这定义了一个可以在for循环中使用的生成器，如下所示：

^{pr2}$

这种方法是有效的，因为它避免了构建超过==100限制的投资组合。在

另外，请注意，我们利用了“现金”百分比基本上可以是任何东西的事实，所以它只占了100%与其他投资类别总和之间的差额。在

以下函数将此循环推广到任意数量的投资类别：

def gen_portfolio(categories):
  n = len(categories)
  tarr = [0] * (n+1)
  parr = [0] * (n+1)
  karr = [0] * (n+1)
  marr = [ len(c) for c in categories ]
  i = 0
  while True:
    while True:
      if i < n:
        p = categories[i][ karr[i] ]
        t = tarr[i] + p
        if t <= 100:
          parr[i] = p
          tarr[i+1] = t
          i += 1
          karr[i] = 0
          continue
        else:
          break                   # backup
      else:
        parr[n] = 100 - tarr[n]   # set the Cash percentage
        yield parr[:]             # yield a copy of the array parr
        break
    # backup
    while True:
      if i > 0:
        i -= 1
        karr[i] += 1
        if karr[i] < marr[i]: break
      else:
        return  # done!

def portfolios2():
  cats = [ [ 10, 15, 20, 25, 30 ], [ 25, 30, 35, 40, 45, 50 ], [ 10, 15, 20 ], [ 20, 25, 30, 35, 40, 45, 50 ] ]
  return gen_portfolio(cats)

下面是一个测试，证明它们产生了相同的结果：

def compareTest():
  ports1 = [ x for x in portfolios() ]
  ports2 = [ x for x in portfolios2() ]
  print "ports1 length:", len(ports1)
  print "ports2 length:", len(ports2)
  for x in ports1:
    if x not in ports2: print "not in ports2:", x
  for x in ports2:
    if x not in ports1: print "not in ports1:", x

更新

下面是一个示例，它演示了此方法与itertools.product. 在

假设有10个投资类别，每个类别的百分比为[90,91，…，99]。带有break语句的嵌套循环将按如下方式进行：

start the loop: for p1 in [90,91,..,99]

  set p1 = 90
  p1 < 100 so continue

  start the loop: for p2 in [90,91,..,99]
    set p2 = 90
    p1 + p2 > 100, so break out of the p2 loop

  set p1 = 91

  p1 < 100 so continue
  start the loop: for p2 in [90,91,..,99]
    set p2 = 90
    p1 + p2 > 100, so break out of the p2 loop
  set p1 = 92
  ...

因此，带有break语句的嵌套循环只查看10种情况—p1=90，91，…，99和p2=90。p2永远不会得到大于90的值，也不会尝试给p3，p4，…，p10赋值。在

另一方面，itertools.product将生成所有100个案例，然后您必须筛选出总和大于100的组合。在

对于某些输入itertools.product因为它是用C编写的，所以它可能会更快，但它不会根据当前选择的总和对案例进行任何修剪。在