Dynamic Programming/Memoization (트리플렛 계산)

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는 마스터 목록에서 7 앞에 오는 11보다 앞에옵니다).

은 카운터 예제를 명확히하기 위해 : 9 내가 감소의 수를 계산하려고 15

보다 이전 하위 목록에서 오는 있기 때문에 (15, 9, 8) 감소 삼중를하지 않을 것 다이내믹 프로그래밍이나 메모를 사용하는 세 쌍둥이. 다음과 같이 루프 구조를 설정하기는 쉽습니다.

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 

그러나 큰 목록의 경우에는 확장되지 않습니다. 나는 한 번 목록을 통과함으로써 삼중 항을 세는 어떤 방법이 있어야하는 것처럼 느낀다. 예를 들어, 하나의 숫자가 다른 숫자보다 크다는 것을 안다면 (또는 내가 얼마나 많은 숫자를 알고 있는지 알 경우) 나중에 해당 정보를 다시 사용할 수 있어야합니다.

예를 들어, 유효한 트리플 셋에서 7 또는 1 앞에 오는 16 개를 알 수 있습니다. 그것은 2 "쌍입니다." 그러므로 내가 목록에서 뒤로 가면서 삼중 항을 만들려하고 19면을 보면, "16보다 크다"라고 말할 수 있어야합니다. 그러므로 우리는 알고 있기 때문에이 두 쌍둥이를 만들 수 있습니다. 16은 2보다 큽니다. " 등등.

저는 소리내어 생각하고 있지만 약간의 통찰력을 고맙게 생각합니다.

Answer 1

을보십시오. 현재 삼중 항의 마지막 요소를 추적하십시오. 메모를 사용하여 효율적으로 만드십시오.

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

는 0 대신 중첩 루프의 n 사이에 인덱스 i를 사용하여 다음과 같은 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