動態編程/記憶（計數三元組）

Question

我有一個像這樣的數字列表（隨機生成，在每個子組中排序的數字。這些組是不相交的，這意味着您不會在多個組中找到給定數字）：

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的數字。「等等。

我只是想大聲，但會很感激一些見解。

Answer 1

使用索引i0和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) 

Answer 2

請嘗試以下解決方案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