In the accounting department I am working for we are from time to time confronted to the following problem:
A customer sends us a check for a given amount, but without specifying what invoices it cancels. It is up to us to find out which ones the payment corresponds to. For example, say that the customer has the following outstanding invoices: $300, $200, $50; and say that the check is for $250. This time it is clear, the customer is paying bills $200 and $50. However, let's now say that the outstanding invoices are $300, $200, $100 and that the check is for $300. In this case there are already two possibilities. The customer is paying the $300 invoice or the $200 and $100. In other words, there is more than one solution to the problem. 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 1.a. first approach using "brute force", that is, exploring all different combinations: every single invoice, all of 2-element tuples, 3-element tuples, etc... 1.b can all the solutions be found without exploring all possible combinations? some problems can be solved by discarding some invoices, for example those whose amounts are greater than the amount of the check. Any ideas? My second question is: 2. this time there are also credit notes outstanding, that is, invoices with negative amounts. For example, I=[500, 400, -100, 450, 200, 600, -200, 700] and a check Ch=600 2.a is the "brute force" method used in 1.a still applicable now that "I" contains negative values? 2.b same as 1.b. However, this time I can imagen that the number of invoices that can be discarded is a lot more reduced. I am a fan of Python, which I find very elegant, powerful and easy to develop with. I would like to find answers to the problems described above, partially because I am still learning python, and I would like to make use of it. Can anybody help? -- http://mail.python.org/mailman/listinfo/python-list