[vsoler] > 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.
I worked on a similar problem involving frequent bank deposits (the bank recorded only the amount of the deposit with no other tracking information to let us know which store made the deposit) and reconciling those deposits to general ledger entries. As pointed-out by others, the purest statement of the problem is computationally unfeasible; however, the real-world application can provide useful heuristics to that limit the search space. 1) Dates can be used to provide some alignment. Customers tend to pay the oldest invoices first and they don't pay before the first invoice is sent. Also, there can be a typical time lag that helps identify where to start a search (i.e. the customer typically takes 45 days to pay an invoice). 2) Search smallest groupings first (eliminate exact matches) then groupings of two items and groupings of three items. 3) Sometime the values on the list possess properties that make them stand-out and easier to match-up. Given invoices of [10, 11, 12, 1000, 13, 14], the 1000 should be easy to match-up in any grouping of payments. Likewise, when looking for groupings, start with the most unique values. Given [2, 2, 2, 3, 3, 5, 5, 5, 6.1, 7], start by trying to match the 6.1 since there is only one occurrence. Raymond -- http://mail.python.org/mailman/listinfo/python-list
