Dit weekend had ik voor mezelf een klein vraagstuk gemaakt.

Na aankopen te doen bij de lokale Carrefour waren we (mijn vrouw en ik) 111,37€ armer, en hebben we daarbij 4 maaltijdcheques gebruikt van 7 euro. Nu vroeg ik me dus af; van al die bedragen op het kasticket, welke bedragen moet ik optellen om tot exact 28 euro (4 maal 7) te komen en hierbij enkel rekening houdend met voedingswaren.

Aangezien mijn liefde voor Python, begon ik in die taal te programmeren en schreef ik het volgende programma:

from copy import copy

class NietGevonden(Exception):
    pass

def probeer_te_vinden(totaal, lijst):
   if totaal == 0:
       return []
   if totaal < 0:
       raise NietGevonden
   for getal in lijst:
       try:
           mijn_lijst = copy(lijst)
           mijn_lijst.remove(getal)
           antwoord = probeer_te_vinden(totaal - getal, mijn_lijst)
           antwoord.append(getal)
           return antwoord
       except NietGevonden:
           pass
   raise NietGevonden

Het programma werkte maar is verre van snel. Maar snel was die avond geen vereiste. De oplossing van het probleem was dat wel en daaraan voldoed dit programma.

Dat het programma niet snel is, wist ik al tijdens de ontwikkeling ervan. Gebruik van een Exception als deel van de oplossing en de copy-operatie per recursie en per lus.

De volgende reeks is traag:

lijst = [2.79,5.38,11.99,3.79,2.69,0.89,1.49,3.99,1.03,1.29,0.88,1.69,2.49,2.69,
         2.79,3.25,1.49,1.65,1.49,3.64,3.28,4.24,1.99]
probeer_te_vinden(20.50, lijst)

Maar vandaag is een andere dag, en wil ik op zoek naar een snellere oplossing. Ik kan uiteraard proberen mijn algoritme te verbeteren maar nog beter is een bestaand algoritme opzoeken en analyseren. kwestie van het wiel niet opnieuw te moeten uitvinden.

Via google en de zoekstring: <<<python try different numbers best combination>>> kwam ik op de volgende site: http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum

Daar staat een Python-oplossing anders dan de mijne, maar het was niet die oplossing die mijn aandacht trok.

def subset_sum_recursive(numbers,target,partial):
    s = sum(partial)

    #check if the partial sum is equals to target
    if s == target: 
        print "sum(%s)=%s"%(partial,target)
    if s >= target:
        return # if we reach the number why bother to continue
    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum_recursive(remaining,target,partial + [n])


def subset_sum(numbers,target):
    #we need an intermediate function to start the recursion.
    #the recursion start with an empty list as partial solution.
    subset_sum_recursive(numbers,target,list())

Er staat ook een Haskell-oplossing die maar 1 regel bedraagd:

filter ((==) 12345 . sum) $ subsequences [1,5,22,15,0,..]

En dan de versie waarmee ik verder heb zitten spelen:

filter ((==) 27 . sum) $ subsequences [1,5,22,16,11]

Ik ken Haskell totaal niet (!), maar ik kwam al snel op de volgende site uit: http://tryhaskell.org/
Daar kon ik die code even snel uitproberen zonder Haskell te moeten installeren.
En inderdaad, het werkte:

=> [[5,22],[16,11]

Ik weet graag hoe zaken werken, dus typte ik gewoon <<<subsequences [1,5,22,16,11]>>> in.
Met als resultaat:

=> [[],[1],[5],[22],[16],[11],[1,5],[1,22],[1,16],[1,11],[5,22],[5,16],[5,11],[22,16],[22,11],[16,11],[1,5,22],[1,5,16],[1,5,11],[1,22,16],[1,22,11],[1,16,11],[5,22,16],[5,22,11],[5,16,11],[22,16,11],[1,5,22,16],[1,5,22,11],[1,5,16,11],[1,22,16,11],[5,22,16,11],[1,5,22,16,11]]

Waarom heeft Python zoiets niet? Na ongeveer een half uur googlen en lezen in de Python docs, kwam ik de "powerset"-functie tegen.

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

Die powerset-snippet doet dus hetzelfde als Haskell's subsequences-functie:

>>>list(powerset([1,5,22,16,11]))
[(), (1,), (5,), (22,), (16,), (11,), (1, 5), (1, 22), (1, 16), (1, 11), (5, 22), (5, 16), (5, 11), ...]

NOTA: de powerset-functie vereist wel Python 2.6, want "chain.from_iterable" is pas dan toegevoegd:
http://docs.python.org/whatsnew/2.6.html

Op rosettacode (http://rosettacode.org/wiki/Power_set) staat nog een andere Python powerset-versie, welke compatibel is met oudere Python-versies:

def powerset(s):
    r = [[]]
    for e in s:
        r += [x+[e] for x in r]
    return r

NOTA: deze powerset-functie (powersetlist) geeft een iets andere volgorde van de list-elementen

Nu we dit weten en nadat we powerset gedefinieerd hebben, kunnen we de Haskell-oneliner converteren naar zijn Python-versie:

filter(lambda x: sum(x) == 27, powerset([1,5,22,16,11]))

Dus in plaats van mijn eerste Python-versie, zie bovenaan, was de bovenstaande one-liner genoeg geweest! Er is wel een belangrijk verschil, mijn versie geeft maar één resultaat, het eerste dat hij tegenkomt. De powerset-variant levert alle mogelijke resultaten (en is sneller). Woops!

NOTA: om de getallen wat leesbaarder te maken: map(lambda getal: format(getal, ".2f"), getallen)

30-01-2012, 00:00 Geschreven door Fibergeek