Wie ändert man diese rekursive Funktion (gibt eine Liste von Pfaden für eine 3X3-Matrix zurück) in iterative Funktion in Python 2.7?

Question

Die folgende rekursive Funktion hilft dabei, alle Pfade für eine 3X3-Matrix von oben links nach unten rechts zu finden, entweder nach unten oder nach rechts. Aber ich möchte es in eine iterative Funktion umwandeln, so dass ich die Funktion bearbeiten kann, um einen bestimmten vervollständigten Pfad zu finden (nur 1, von links oben nach rechts unten, nach rechts oder unten), der zusammenfasst (Summe der Werte bei jeder Punkt entspricht einer festgelegten Anzahl) einer gewünschten Anzahl, z. 12. Dies ist besonders wichtig für eine größere Matrix z. eine 9 x 1000-Matrix. Wie mache ich es?

Hinweis für Danoran:
Die Werte sind immer positiv. Wenn Sie sich meine 3X3-Matrix a ansehen, sehen Sie Werte von 1s, 2s und 3s. So ist zum Beispiel die Bewegung von 1 zu 1 zu 1 zu 2 zu 3 (Ziel) ein abgeschlossener Pfad und die Summe ist 8.

Dies findet nur alle Pfade.

a = [] 
for i in range(3): 
    r = [] 
    for j in range(3): 
     r.append(i+1) 
    a.append(r) 

a = Matrix

all_paths = [] 

def printall(currentRow, currentColumn, nums): 
    if (currentRow == len(a) - 1): 
     for i in range(currentColumn, len(a[0])): 
      nums.append(a[currentRow][i]) 
     all_paths.append(nums) 
     return all_paths 

    if (currentColumn == len(a[0]) - 1): 
     for i in range(currentRow, len(a)): 
      nums.append(a[i][currentColumn]) 
     all_paths.append(nums) 
     return all_paths 

    nums.append(a[currentRow][currentColumn]) 
    printall(currentRow+1, currentColumn, nums[:]) 
    printall(currentRow, currentColumn+1, nums[:]) 

printall(0,0,[]) 

print all_paths 

Answer 1

Wenn es R Zeilen und C Spalten, müssen Sie mache R-1 Down-Jumps und C-1 Right-Jumps. Das ist invariant. Die einzige Variation ist in der Reihenfolge die Sprünge. Wenn wir dj = R-1 und rj = C-1 sagen, dann ist die Gesamtzahl der Pfade (dj + rj)!/(Dj! Rj!).

So können wir einfach durch alle einzigartigen Permutationen iterieren. Beachten Sie, dass itertools.permutations()alle Permutationen generiert, nicht nur die einzigartigen, so müssen wir die Wiederholungen herausfiltern. Natürlich bedeutet diese auch, dass die Laufzeit proportional zu (dj + rj) !, die Anzahl der nicht eindeutigen Permutationen sein wird. Ich werde nicht gehen, um einzigartige Permutationen effizient zu generieren; siehe beispielsweise Question 22431637.

Im folgenden Code habe ich die Anzahl der Zeilen auf 4 erhöht, um Zeilen von Spalten zu unterscheiden.

from itertools import permutations 

a = [] 
for i in range(4): 
    r = [] 
    for j in range(3): 
     r.append(i+1) 
    a.append(r) 

#print a # Uncomment to trace execution 

all_paths = [] 

def gen_all_paths(matrix): 
    rows = len(matrix) 
    cols = len(matrix[0]) 
    dj = rows - 1 # down-jumps 
    rj = cols - 1 # right-jumps 
    pathmix = 'd' * dj + 'r' * rj 

    prev =() 
    for path in permutations(pathmix): 
     if path <= prev: # filter out repeats 
      continue 
     prev = path 

     r, c = 0, 0 
     cells = [matrix[0][0]] 
     for i in path: 
      if i == 'd': 
       r += 1 
      else: 
       c += 1 
      cells.append(matrix[r][c]) 
     #print ''.join(path), cells # Uncomment to trace execution 
     all_paths.append(cells) 

gen_all_paths(a) 

print all_paths