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