Dynamische Programmierung/Memoization (Triplets zählen)

Question

Ich habe eine Liste von Zahlen so (zufällig generierte, Zahlen innerhalb jeder Untergruppe sortiert. Die Gruppen sind disjunkt, was bedeutet, dass Sie keine gegebene Nummer in mehr als einer Gruppe finden):

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

ich Zählung die Anzahl der Möglichkeiten versuche ich ein abnehm-Triplett zu schaffen.

Ein abnehmendes Triplet ist ein Triplet, in dem wir die Liste von links nach rechts scannen und Element 1 aus einer Gruppe ausreißen, dann Element 2 aus einer anderen Gruppe, dann Element 3 aus einer anderen Gruppe, wobei das Endergebnis abnehmen sollte natürlich bestellen.

Zum Beispiel ist (19,11,7) ein gültiges abnehmendes Triplett, weil diese Zahlen aus verschiedenen Unterlisten kommen und in abnehmender, natürlicher Reihenfolge sind (19 kommt vor 11, das vor 7 in der Masterliste steht).

mit einem Gegenbeispiel Zur Verdeutlichung: (15, 9, 8), würde eine abnehm Triplett nicht sein, weil die 9 wird von einem früheren sublist als 15 I

kommen versuche die Anzahl der abnehm zu zählen Drillinge mit dynamischer Programmierung oder Memoisierung irgendeiner Art. Es ist einfach genug, eine Schleifenstruktur wie folgt einzurichten:

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 

Aber es skaliert nicht sehr gut für größere Listen. Ich denke, es sollte eine Möglichkeit geben, Triplets zu zählen, indem man die Liste einmal durchgeht. Wenn ich zum Beispiel weiß, dass eine Zahl größer ist als eine andere (oder wenn ich weiß, wie viele Zahlen größer sind als), habe ich das Gefühl, dass ich diese Informationen später wieder verwenden kann.

Zum Beispiel weiß ich 16 kann vor 7 oder 1 in einem gültigen Triplet kommen. Das sind 2 "Paare." Wenn ich also versuche, ein Triplet zu erstellen, wenn ich rückwärts in der Liste gehe, und ich beispielsweise 19 anschaue, sollte ich sagen können: "Es ist größer als 16, daher können Sie daraus zwei Triplets erstellen, weil wir es wissen 16 ist größer als 2 Zahlen. " und so weiter.

Ich denke nur laut auf, würde aber etwas Einsicht zu schätzen wissen.

Answer 1

Verwenden eines Index i zwischen 0 und n anstelle von verschachtelten Schleifen. Behalten Sie das letzte Element des aktuellen Triplets im Auge. Und verwenden Sie ein Memo, um es effizient zu machen.

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

Versuchen die folgende Lösung 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