My own accounting python euler problem

[Raymond Hettinger]

[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