Ist es möglich, die Rekursion aus dieser Funktion zu entfernen?

Ich habe mit diesem eine Weile gespielt und kann einfach keine offensichtliche Lösung sehen. Ich möchte die Rekursion aus der XinY_Go-Funktion entfernen.

def XinY_Go(x,y,index,slots): if (y - index) == 1: slots[index] = x print slots slots[index] = 0 return for i in range(x+1): slots[index] = xi XinY_Go(x-(xi), y, index + 1, slots) def XinY(x,y): return XinY_Go(x,y,0,[0] * y) 

Die Funktion berechnet die Anzahl der Möglichkeiten, um X-Marmor in Y-Slots zu setzen. Hier ist ein Beispielausgang:

  >>> xy.XinY (1,2)
  [1, 0]
  [0, 1]
  >>> xy.XinY (2,3)
  [2, 0, 0]
  [1, 1, 0]
  [1, 0, 1]
  [0, 2, 0]
  [0, 1, 1]
  [0, 0, 2]

3 Solutions collect form web for “Ist es möglich, die Rekursion aus dieser Funktion zu entfernen?”

Eine naive Umsetzung von @Joel Coehoorns Vorschlag folgt:

 def XinY_Stack(x, y): stack = [(x, 0, [0]*y)] while stack: x, index, slots = stack.pop() if (y - index) == 1: slots[index] = x print slots slots[index] = 0 else: for i in range(x + 1): slots[index] = xi stack.append((i, index + 1, slots[:])) 

Beispiel:

 >>> XinY_Stack(2, 3) [0, 0, 2] [0, 1, 1] [0, 2, 0] [1, 0, 1] [1, 1, 0] [2, 0, 0] 

Basierend auf itertools.product

 def XinY_Product(nmarbles, nslots): return (slots for slots in product(xrange(nmarbles + 1), repeat=nslots) if sum(slots) == nmarbles) 

Basierend auf verschachtelten Loops

 def XinY_Iter(nmarbles, nslots): assert 0 < nslots < 22 # 22 -> too many statically nested blocks if nslots == 1: return iter([nmarbles]) # generate code for iter solution TAB = " " loopvars = [] stmt = ["def f(n):\n"] for i in range(nslots - 1): var = "m%d" % i stmt += [TAB * (i + 1), "for %s in xrange(n - (%s)):\n" % (var, '+'.join(loopvars) or 0)] loopvars.append(var) stmt += [TAB * (i + 2), "yield ", ','.join(loopvars), ', n - 1 - (', '+'.join(loopvars), ')\n'] print ''.join(stmt) # exec the code within empty namespace ns = {} exec(''.join(stmt), ns, ns) return ns['f'](nmarbles + 1) 

Beispiel:

 >>> list(XinY_Product(2, 3)) [(0, 0, 2), (0, 1, 1), (0, 2, 0), (1, 0, 1), (1, 1, 0), (2, 0, 0)] >>> list(XinY_Iter(2, 3)) def f(n): for m0 in xrange(n - (0)): for m1 in xrange(n - (m0)): yield m0,m1, n - 1 - (m0+m1) [(0, 0, 2), (0, 1, 1), (0, 2, 0), (1, 0, 1), (1, 1, 0), (2, 0, 0)] 

Alles, was wir als Rekursion denken, kann auch als Stack-basiertes Problem gedacht werden, wo die rekursive Funktion nur den Call-Stack des Programms verwendet, anstatt einen separaten Stack zu erstellen. Das bedeutet, dass jede rekursive Funktion mit einem Stapel umgeschrieben werden kann.

Ich weiß nicht, python gut genug, um Ihnen eine Umsetzung, aber das sollte Sie in die richtige Richtung zeigen. Aber in einer Nußschale, drücken Sie die ersten Argumente für die Funktion auf den Stack und fügen Sie eine Schleife, die läuft, solange die Größe des Stapels größer als Null ist. Pop einmal pro Loop-Iteration, schieben jedes Mal, wenn sich die Funktion gerade nennt.

Schauen Sie sich diesen Code für die Erstellung aller Permutationen, ich glaube, ich wäre relativ einfach, etwas ähnliches für Ihr Problem zu implementieren.

Wie generiere ich alle Permutationen einer Liste in Python?

  • Python-Rekursions- und return-Anweisungen
  • Wie man sogar und ungerade Zahlen eines Arrays mit Rekursion summiert
  • Das max-Element in einer Sequenz mit Rekursion zu finden
  • Lock-Kombinationen für dynamische Sperrgröße
  • Python max Rekursion, Frage über sys.setrecursionlimit ()
  • N-Queen-Backtracking in Python: Wie gibt man Lösungen zurück, anstatt sie zu drucken?
  • Rekursiv finden Sie die kth größte int in Liste der Liste der int in Python
  • Rekursiv finden Sie alle Münzkombinationen, die eine bestimmte Menge produzieren
  • Python-Rekursions-Permutationen
  • Rekursionsfunktion funktioniert nicht richtig
  • Python leer dict nicht durch Verweis übergeben?
  • Python ist die beste Programmiersprache der Welt.