Python - Summe N in spezifische Summanden K zerlegen?

Moin, ich suche einen effizienten Algorithmus:

Gegeben ist eine Zahl N zwischen 1 - 12. Diese Zahl soll in Summanden zerlegt werden. So wenig wie möglich und jedes Element von K darf nur 1-mal vorkommen.

Dabei stehen aber nur bestimmte Summanden zur Verfügung (ähnlich wie Primfaktorzerlegung)

Beispiel:

N = 10
K = 1, 1, 2, 3, 5

Lösung:
5 + 3 + 2 = 10

N = 2
K = 1, 1, 2, 3, 5

Lösung:
2

Noch besser wäre eine aufsteigende Liste der Möglichkeiten von kurz zu lang, also zum Beispiel

N = 2
K = 1, 1, 2, 3, 5

Lösung:
2
1 + 1

N = 10
K= 1, 1, 2, 3, 5

Lösung:
5 + 3 + 2
5 + 3 + 1 + 1

Hat jemand Ideen? :)

Answer 1

[ralphdieter]

Ich löse solche Probleme gern rekursiv. Hier läuft es darauf hinaus, einen Summanden k∈K

• zu verwenden und mit jeder Lösung von (N-k, K\k) zu ergänzen,
• nicht zu verwenden und alle Lösungen von (N, K\k) zu nehmen.

In dieser Form ist es eine rekursive Aufzählung aller Teilmengen von k. Aber die kann man drastisch abkürzen, wenn man abbricht, sobald zu wenig Summanden übrig sind (Σk<N). Das ist besonders effektiv, wenn man stets den größten Wert k∈K wählt. Wenn K aufsteigend sortiert ist, ist das immer der letzte Wert k[-1]:

def as_sum(n, k):
    """ generate all sub-lists of k with sum(k)==n """

    if n==0:
        yield ()  # the only solution
        return

    if n<0:
        return    # not feasible

    if sum(k)<n:
        return    # not feasible

    # A) use k[-1]:
    for s in as_sum(n-k[-1], k[:-1]):
        yield (k[-1],)+s  # k[-1]+Σs==n

    # B) ignore k[-1]:
    for s in as_sum(n, k[:-1]):
        yield s

# Test:
for s in sorted(as_sum(10, (1,1,2,3,5)), key=len): 
    print(s)

Doppelte Einträge in K produzieren allerdings auch doppelte Lösungen. Das kannst Du vermeiden, indem Du in der zweiten for-Schleife nicht nur das übergangene Element k[-1], sondern auch alle seine Kopien aus k entfernst:

   # B) ignore k[-1] and its duplicates:
   for s in as_sum(n, tuple(i for i in k if i!=k[-1])):
       yield s

# Test 2:
for s in as_sum(12, tuple(i//12+1 for i in range(144))):
    print(s)

Das läuft so weit schon ziemlich flott, aber natürlich ist da noch Luft nach oben. Vor allem ist es unnötig teuer, ständig Teilmengen von K zu erzeugen. Mit der Originalliste und einer erlaubten Länge sollte alles wesentlich schneller gehen. Solche Optimierungen macht man aber erst, wenn die Laufzeit ein Problem wird.

Comments

[Dijkstra3006]

Vielen, vielen Dank!! Genau so hab ich mir das vorgestellt!! ;)