Re: My own accounting python euler problem

[Ozz]

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





--
http://mail.python.org/mailman/listinfo/python-list

Re: My own accounting python euler problem

[Ozz]

Oops,

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, []]


better to check for the empty set too, thus;

if (len(L) == 0):
return [[]]

The order of the sets looks better too;

>>> subset.subsets([1,2,3])
[[], [1], [2], [2, 1], [3], [3, 1], [3, 2], [3, 2, 1]]

cheers,



--
http://mail.python.org/mailman/listinfo/python-list

Re: My own accounting python euler problem

[Ozz]

Robert P. J. Day schreef:

  does your solution allow for the possibility of different invoices
of equal amounts?  i would be reluctant to use the word "subset" in a
context where you can have more than one element with the same value.


I think it handles different invoices of equal amounts correctly.
I agree with you though that the term subset may not be the best name in 
this context because of those duplicates.


cheers,
Ozz
--
http://mail.python.org/mailman/listinfo/python-list

Re: My own accounting python euler problem

[Ozz]

Dan Bishop schreef:


You can avoid the S list my making it a generator:

def subsets(L):
if L:
for s in subsets(L[1:]):
yield s
yield s + [L[0]]
else:
yield []


Nice one. Thanks!

Ozz
--
http://mail.python.org/mailman/listinfo/python-list

Re: My own accounting python euler problem

[Ozz]

vsoler schreef:


Instead of subsets, do you mean permutations/combinations?  Since 2
invoices can have the same amount perhaps the terms permutation is
better.



As some other poster already suggested 'powerset' ( 
http://en.wikipedia.org/wiki/Power_set ) may be a better name, except 
for those duplicates, of course. On the other hand, I think viewing it 
as a powerset is the most 'natural' in this case. (imo permutations are 
about the order of objects, not about whether the objects are included 
in a set or not)


cheers,
Ozz

--
http://mail.python.org/mailman/listinfo/python-list