Ozz wrote:
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.
Here's my own take on it:
def list_possible_invoices(invoices, check):
if check:
# The check hasn't yet been fully consumed.
for index, inv in enumerate(invoices):
# If this invoice doesn't exceed the check then it consume
some of the check.
if inv <= check:
# Try to consume the remainder of the check.
for inv_list in list_possible_invoices(invoices[index +
1 : ], check - inv):
yield [inv] + inv_list
else:
# The check has been fully consumed.
yield []
invoices = [500, 400, 450, 200, 600, 700]
check = 600
# List all the possible subsets of invoices.
# Sorting the invoices first in descending order lets us reduce the
number of possibilities to try.
for inv_list in list_possible_invoices(sorted(invoices, reverse=True),
check):
print inv_list
--
http://mail.python.org/mailman/listinfo/python-list
