Ich habe Probleme mit einem Rekursionsproblem, das nicht zu schwierig sein sollte, aber aus irgendeinem Grund finde ich keine Lösung.

Ich habe ein Array der Größe "n" und möchte jedes Element von 0 bis n so hochzählen, dass ich jede mögliche Kombination erhalte.

n = 3
[0,0,0]
[0,0,1]
[0,1,0]
[1,0,0]
[...  ]
[3,3,3]

Kann jemand helfen?

0
Trollbrot 11 Dez. 2012 im 21:22

3 Antworten

Beste Antwort

Keine (explizite) Rekursion erforderlich:

import itertools
for comb in itertools.product(range(4), repeat=3):
    print comb

Produziert:

(0, 0, 0)
(0, 0, 1)
(0, 0, 2)
(0, 0, 3)
(0, 1, 0)
(0, 1, 1)
...
(3, 3, 2)
(3, 3, 3)
1
Ned Batchelder 11 Dez. 2012 im 17:29

Hier ist eine Möglichkeit, die das Verfahren sehr explizit macht:

def combinations(n, elements = None):
    if elements == 0: return [[]]

    if not elements: elements = n

    result = []
    for v in range(n + 1):
        for subcombination in combinations(n, elements - 1):
            result.append([v] + subcombination)

    return result

Es gibt mehr pythonische Möglichkeiten, um eine bessere Leistung zu erzielen, einschließlich Verständnis oder Generatoren, aber es scheint, als würden Sie nach einer expliziten Implementierung suchen.

0
recursive 11 Dez. 2012 im 17:29

Wenn Sie es selbst codieren und die Rekursion verwenden müssen:

def gen(n, l, prefix=()):
  if l == 0:
    print prefix
  else:
    for i in range(n):
      gen(n, l - 1, prefix + (i,))

gen(4, 3)
3
NPE 11 Dez. 2012 im 17:32