My own accounting python euler problem

Ozz notvalid at wathever.com
Sun Nov 8 11:43:42 CET 2009


Hi,

> My first question is:
> 1. given a list of invoives I=[500, 400, 450, 200, 600, 700] and a
> check Ch=600
> how can I print all the different combinations of invoices that the
> check is possibly cancelling
> 

Incidentally, I'm currently learning python myself, and was working on 
more or less the same problem as an exercise;

For listing all different subsets of a list (This is what I came up 
with. Can it be implemented shorter, btw?):

def subsets(L):
         S = []
         if (len(L) == 1):
                 return [L, []]
         else:
                 for s in subsets(L[1:]):
                         S.append(s)
                         S.append(s + [ L[0]])
         return S

Now, to use the above piece of code (after 'import subset'):

 >>> subset.subsets([4,7,8,2])
[[2], [2, 4], [2, 7], [2, 7, 4], [2, 8], [2, 8, 4], [2, 8, 7], [2, 8, 7, 
4], [], [4], [7], [7, 4], [8], [8, 4], [8, 7], [8, 7, 4]]
 >>> map(sum,subset.subsets([4,7,8,2]))
[2, 6, 9, 13, 10, 14, 17, 21, 0, 4, 7, 11, 8, 12, 15, 19]

It's not a real solution yet, and as others have pointed out the problem 
is NP complete but it might help to get you going.

cheers,
Ozz








More information about the Python-list mailing list