1

我有一个这样的数字列表（随机生成，在每个子组中排序的数字。这些组是不相交的，这意味着您不会在多个组中找到给定的数字）：

L=[[19,18,14,9,4],[15,12,11,10,6,5],[8],[16,13,3,2],[17,7,1]]

我正在尝试计算可以创建递减三元组的方法数量。

递减三元组是一个三元组，我们从左到右扫描列表并从一组中取出元素 1，然后从另一组中取出元素 2，然后从另一组中取出元素 3，其中最终结果自然应该按递减顺序排列。

例如，(19,11,7) 是一个有效的递减三元组，因为这些数字来自不同的子列表并且按递减的自然顺序排列（19 在主列表中的 11 之前，在 7 之前）。

用一个反例来澄清：(15, 9, 8) 不会是一个递减的三元组，因为 9 来自比 15 更早的子列表。

我正在尝试使用动态编程或某种记忆来计算递减三元组的数量。像这样设置循环结构很容易：

for i in xrange(0,len(L)-2):
    for j in xrange(i+1, len(L)-1):
        for k in xrange(j+1, len(L)):
            for item1 in L[i]:
                for item2 in L[j]:
                    if item1>item2:
                        for item3 in L[k]:
                            if item2>item3:
                                count+=1

但是对于较大的列表，它不能很好地扩展。我觉得应该有一些方法可以通过遍历列表一次来计算三胞胎。例如，如果我知道一个数字大于另一个数字（或者如果我知道它大于多少个数字），我觉得我应该能够在以后重新使用该信息。

例如，我知道 16 可以在有效的三元组中出现在 7 或 1 之前。那是2个“对”。因此，如果我想在列表中倒退时创建一个三元组，例如，我查看 19，我应该能够说“它大于 16，因此您可以从中创建两个三元组，因为我们知道16 大于 2 个数字。” 等等。

我只是在大声思考，但希望能得到一些见解。

4

2 回答 2

0

尝试以下 itertool 解决方案

import itertools
import time

L= [
    {19, 18, 14, 9, 4},
    {15, 12, 11, 10, 6, 5},
    {8},
    {16, 13, 3, 2},
    {17, 7, 1},
]


start = time.time()
for i in xrange(20000):
    count = 0
    for i in xrange(0,len(L)-2):
        for j in xrange(i+1, len(L)-1):
            for k in xrange(j+1, len(L)):
                for item1 in L[i]:
                    for item2 in L[j]:
                        if item1>item2:
                            for item3 in L[k]:
                                if item2>item3:
                                    count+=1

print
print time.time() - start

# result: 3.1542930603

start = time.time()
for i in xrange(20000):
    sum(1 for l1, l2, l3 in itertools.combinations(L, 3) for a, b, c in itertools.product(l1, l2, l3) if a > b > c)

print
print time.time() - start

# result: 1.94973897934
于 2012-04-13T20:01:35.207 回答
0

i在和之间使用索引0而n不是嵌套循环。跟踪当前三元组的最后一个元素。并使用备忘录使其高效。

L=[[19,18,14,9,4],[15,12,11,10,6,5],[8],[16,13,3,2],[17,7,1]]

n=len(L)

memo = {}
def f(i,j,last):
  if (i,j,last) in memo:
    return memo[(i,j,last)]
  if j==3:
    return 1
  if i==n:
    return 0
  res=0
  # take one from L[i]
  for x in L[i]:
    if last > x:
      res+=f(i+1,j+1,x)
  # don't take any element from L[i]
  res += f(i+1,j,last)
  memo[(i,j,last)] = res
  return res

BIG = 10**9
print f(0,0,BIG)
于 2012-04-13T20:11:29.647 回答