Summanden aus Zahl ermitteln

[Siegfried]

Guten Morgen aus dem sonnigen, aber kalten Hamburg,

ich möchte aus einer Zahl die möglichen Summanden ermitteln und habe mir dafür folgende Funktion überlegt:

[codebox=python file=Unbenannt.txt]def finde2summanden(summe,max_summand=9, min_summand = 1):
max_summand += 1
return [(i,j) for i in xrange(min_summand, max_summand) \
for j in xrange(i+1 , max_summand) if i + j == summe]

[/code]Durch die Voreinstellungen min_summand und max_summand sind die Ergebnisse auf den Bereich zwischen 1 und 9 begrenzt. Im 2. xrange entfallen durch das i + 1 permutierte Ergebnisse und Ergebnisse mit gleichen Summanden, d.h. finde2summanden(4) ergibt nur [(1,3)]. Durch Einführen eines Modus-Parameters könnten auch wahlweise [(1,3),(2,2)] oder [(1,3),(2,2),(3,1)] erscheinen.

[codebox=python file=Unbenannt.txt]def finde2summanden(summe,max_summand=9, min_summand = 1, modus = "Exclusiv"):
max_summand += 1
if str(modus).upper() == "ALLES":
return [(i,j) for i in xrange(min_summand, max_summand) \
for j in xrange(min_summand, max_summand) if i + j == summe]
elif str(modus).upper() == "DOPPELT":
return [(i,j) for i in xrange(min_summand, max_summand) \
for j in xrange(i , max_summand) if i + j == summe]
else:
return [(i,j) for i in xrange(min_summand, max_summand) \
for j in xrange(i+1 , max_summand) if i + j == summe]

[/code]
Aus Übersichtlichkeitgründen verzichte ich im Folgenden auf die "Modus"-Version. Wenn ich drei oder vier Summanden ermitteln möchte könnte man die Funktion wie folgt variieren:

[codebox=python file=Unbenannt.txt]def finde3summanden(summe,max_summand=9, min_summand = 1):
max_summand += 1
return [(i,j,k) for i in xrange(min_summand, max_summand) \
for j in xrange(i+1 , max_summand) \
for k in xrange(j+1 , max_summand) if i + j + k == summe]

def finde4summanden(summe,max_summand=9, min_summand = 1):
max_summand += 1
return [(i,j,k,l) for i in xrange(min_summand, max_summand) \
for j in xrange(i+1 , max_summand) \
for k in xrange(j+1 , max_summand) \
for l in xrange(k+1 , max_summand) if i + j + k + l == summe]

[/code]Mein Problem ist also: Wenn sich erst zur Progammlaufzeit entscheidet, wieviele Summanden ich haben möchte, kann ich doch nicht vorher 27 Stück findeXXSummanden anlegen. Als Lösung ist mir nur eingefallen, mir einen String zu basteln und dann diesen mit eval() auszuführen. Es funktioniert auch, scheint mir aber viel zu umständlich.

[codebox=python file=Unbenannt.txt]def finde_summanden(summe,anzahl=2,max_summand=9, min_summand = 1):
max_summand += 1
befehl="[("
for i in range(anzahl):
befehl += "j" + str(i) + ","
befehl+=") "
befehl += "for j0 in xrange(min_summand," + str(max_summand) + ") "
for i in range(1, anzahl):
befehl += "for j" + str(i) + " in xrange(j" + str(i-1) + "+1," + str(max_summand) + ") "
befehl += "if j0"
for i in range(1,anzahl):
befehl += "+j" +str(i)
befehl+="==" + str(summe) + "]"
return eval(befehl)
[/code]
Für Verbessungsvorschläge oder ganz andere Ansätze wäre ich dankbar



Siegfried

[Alfons Mittelmeyer]

@Siegfried: Dürfen da auch negative Zahlen dabei sein?

[BlackJack]

@Siegfried: Wenn ich das richtig sehe suchst Du die `itertools.product()`- und die `sum()`-Funktion. Auf jeden Fall *nicht* `eval()`.

Falls Du dann mit der Laufzeit nicht zufrieden bist, könntest Du eine eigene, rekursive Funktion schreiben, denn `product()` geht ja wirklich alle Möglichkeiten durch, man könnte aber sicher so einiges schon verwerfen wenn die Teilsumme schon über dem Ergebnis liegt.

Ausserdem würde ich am Anfang prüfen ob man überhaupt auf die Ergebnissumme kommen kann. Wenn jemand als Summe 1.000.000 übergibt und als Anzahl 2 mit den Grenzen 1 bis 9, dann braucht man ja gar nicht erst anfangen zu suchen.

[BlackJack]

@Siegfried: Ähem, `combinations()` suchst Du natürlich, und nicht `product()`.

Code: Alles auswählen

from itertools import combinations


def finde_summanden(summe, anzahl=2, min_summand=1, max_summand=9):
    return [
        xs for xs in combinations(xrange(min_summand, max_summand), anzahl)
        if sum(xs) == summe
    ]

[Siegfried]

@BlackJack

Vielen Dank für die schnelle Antwort. Mir war klar,daß ich nicht eval() gesucht hatte. Funktioniert zwar, ist aber gebastelt. combinations() kannte ich noch nicht. Funktion sieht deutlich verständlicher und eleganter aus. Als kleiner Flüchtigkeitsfehler ist mir nur aufgefallen, daß max_summand um eins vergrößert werden muß, sonst wird der maximal mögliche Summand nicht berücksichtigt.

Danke nochmals

Siegfried

[Siegfried]

Ich habe noch einmal Rekursion versucht. Ist nicht ganz "sauber", funktioniert aber.

[codebox=pys60 file=Unbenannt.txt]
def finde_summanden(summe, anzahl = 2, max_summand = 9, min_summand = 1):
def finde_rekursiv(summand, rest, anzahl, erg):
if anzahl == 0:
if sum(erg) == summe:
l.append(erg)
else:
for i in xrange(max(min_summand, summand + 1), min(rest, max_summand) + 1):
finde_rekursiv(i, rest-i, anzahl - 1, erg + [i,])


l=list()
finde_rekursiv(0, summe, anzahl, [])
return

[/code]
Es läuft aber sehr langsam . Wenn man die Zahl 25 in fünf Summanden aufteilt und diese 500 Mal wiederholt, benötigt mein Rechner ca 1.17 sec, während die "combinations"-Variante bei gleichen Bedingungen nur 0.1 sec benötigt und eine fünffach geschachtelte list compehension gar nur 0.06 sec.
Wenn man sich bei der Rekursion eine Ebene spart, benötigt es immer noch 0.59 sec.

[codebox=pys60 file=Unbenannt.txt]
def finde_summanden(summe, anzahl = 2, max_summand = 9, min_summand = 1):
def finde_rekursiv(summand, rest, anzahl, erg):
if anzahl == 1:
if sum(erg) + rest == summe and max_summand >= rest > summand:
l.append(erg + [rest])
else:
for i in xrange(max(min_summand, summand + 1), min(rest, max_summand) + 1):
finde_rekursiv(i, rest - i, anzahl - 1, erg + [i,])

l=list()
finde_rekursiv(0, summe, anzahl, [])
return l

[/code]