All possible exact sums from multiple arrays

Question

I've been given the following problem and my code has become a horrible mess and I'm quite stuck.

You are given an allowance to spend at some shops (something like $15, just some positive integer) You may only spend this money under two conditions:

1) You buy exactly one item from each shop.

2) You spend all of your money (nothing left over, and no debt)

Find all possible ways you could have purchased items to satisfy the above.

In actuality, you're given a budget int and some array like

9 and [[1,2,3],[0,5],[2,3,8]]

where each inner array lists the prices of items in the a shop. There can be arbitrarily many shops with arbitrarily many items. Costs cannot be negative, but they can be free!

The expected solution here would be:

[[1,5,3],[2,5,2],[1,0,8]]

As each array contains one item from each shop, each totals 9, and all possibilities are present. Just to make it more difficult, speed is paramount.

The following is my code that has descended into madness and a near complete lack of functionality:

def Stepper(bud,LOL):
    n=len(LOL)
    lasts=[]
    indices=[0 for j in range(n)]
    focus=0
    funds=[0 for j in range(n+1)]
    funds[0]=bud
    sols=[]
    moveable=[]
    for j in range(n):
        length=len(LOL[j])
        if(length==0):
            return []
        lasts.append(length-1)
        if(moveable==[]):
            if(length==1):
                funds[j+1]=funds[j]-LOL[j][0]
            else:
                moveable.append(j)
                focus=j
    while(moveable!=[]):
        while(LOL[focus][indices[focus]] > funds[focus]):
            indices[focus]+=1
        if(indices[focus]==lasts[focus]):
            if(moveable[-1]==focus):
                moveable.remove(focus)
            if(moveable==[]):
                if(focus<n-1):
                    moveable.append(focus+1)
        funds[focus+1]=funds[focus]-LOL[focus][indices[focus]]
        #print(n,lasts,indices,focus,moveable,funds,sols)
        if((funds[focus+1]!=0) and (focus<n-1)):
                focus+=1
                indices[focus]=0
        else:
            if(funds[focus+1]==0):
                for j in range(focus+1,n):
                    indices[j]=lasts[j]
                sols.append(list(indices))
            if(moveable[-1]==n-1):
                moveable.remove(n-1)
            if(moveable!=[]):
                focus=moveable[-1]
                indices[focus]+=1
                if(indices[focus]==lasts[focus]):
                    if(moveable[-1]==focus):
                        moveable.remove(focus)
                    if(moveable==[]):
                        if(focus<n-1):
                            moveable.append(focus+1)
                funds[focus+1]=funds[focus]-LOL[focus][indices[focus]]
                focus+=1
                indices[focus]=0
    return(sols)

where bud is the budget and LOL is the list of lists (the shops and prices)

Answer 1

This is a combinatorics problem. Which item from shop 1 combines with which item from shop 2 and which single items from shops 3...n to add up to some number?

Python's standard library has a function which can generate all these combinations for you, saving you the nested for loops. It's the handy itertools.product:

>>> import itertools
>>> budget = 9
>>> shops = [[1, 2, 3], [0, 5], [2, 3, 8]]
>>> list(itertools.product(*shops))
[(1, 0, 2),
 (1, 0, 3),
 (1, 0, 8),
 (1, 5, 2),
 (1, 5, 3),
 (1, 5, 8),
 (2, 0, 2),
 (2, 0, 3),
 (2, 0, 8),
 (2, 5, 2),
 (2, 5, 3),
 (2, 5, 8),
 (3, 0, 2),
 (3, 0, 3),
 (3, 0, 8),
 (3, 5, 2),
 (3, 5, 3),
 (3, 5, 8)]

Next we want to get rid of all the combinations which do not satisfy our condition (that the prices exactly add up to the total budget). Let's use the built-in filter function to get our solution:

>>> list(filter(lambda prices: sum(prices) == budget, itertools.product(*shops))
[(1, 0, 8), (1, 5, 3), (2, 5, 2)]

Answer 2

If you are allowed to use itertools

import itertools
x =  [[1,2,3],[0,5],[2,3,8]]
combinations = list(itertools.product(*x))
for o in combinations:
    if sum(o) == 9:
        print(o)

Output:

(1, 0, 8)
(1, 5, 3)
(2, 5, 2)

Depends on this question.

Answer 3

If you're still interested in an algorithm this is my solution:

def Stepper(bud, shops, combinations = None):
    if combinations is None:
        combinations = [[item] for item in shops[0]] 
        #if empty, populate  the list of combinations with list containing every item of the first shop
        shops = shops[1:] #remove the shop from the list

    if len(shops) == 1: #if only one shop remains
        counter = 0
        while counter < len(combinations):
            comb = combinations[counter] # take a combination
            diff = bud - sum(comb)       # check how much you have to spend
            if diff in shops[0]: 
                #if the shop have what you're looking for you keep the combination
                comb.append(diff)
                counter += 1
            else:
                # there is no way to spend all the money
                combinations.remove(comb)

        return combinations

    new_combinations = list()
    for old_combination in combinations:
        for item in shops[0]:
            comb = old_combination + [item] #create every possible combination mixing the old combinations with the items of the next stop
            if sum(comb) < bud: new_combinations.append(comb) # the combination is valid only if you have 0 or more money left
    return Stepper(bud,shops[1:],new_combinations) # calculate combinations with the remaining shops

To test it simply call

Stepper(9, [[1,2,3],[0,5],[2,3,8]])

Answer 4

Here is a simple, and probably inefficient, way to solve it.

In [70]: s = [[1,2,3],[0,5],[2,3,8]]    
In [71]: n = 9
In [72]: for x in s[0]:
    ...:     for y in s[1]:
    ...:         for z in s[2]:
    ...:             if x+y+z == n:
    ...:                 print(x,y,z)
    ...:
1 0 8
1 5 3
2 5 2

Starting from the first shop, for any option, iterate over the next store, then again, for any option of the second store, iterate over the options of the next store. Sum up all the prices and check if the sum is equal to 9.