Cheque clearing
Of course, one way is the "brute force" method. I actually implemented
such an approach years ago using a now obsolete computer language on a
now obsolete operating system. I've never ported it to a more modern
system, though it might be a fun spare time project. Here's how it goes:
Say there are N transactions (deposits, cheques, ATM withdrawals, etc.)
that are candidates (i.e., cheques you know have been written and
deposits you have made but that you don't know whether the bank has yet
added/subtracted from your account balance.) Adopt a sign convention
(say positive for "paid ins" like deposits and negative for "paid outs"
like cheques).
Then there are 2^N possible combinations (each transaction can either
have cleared or not) to examine. If N is small enough, this can easily
be implemented on a computer. Just write a program that will read in
your list of transaction amounts and then in turn generates each
possible combination (subset) of them and calculates the corresponding
total. When you find one that matches the difference (100.32 in your
example), then it is possibly the subset consisting of those that
haven't cleared. There is, of course, no guarantee that the solution
will be unique since in general it is possible for several different
subsets to yield the same total. However, without further information,
this is as far as you can narrow it down. BTW, it is probably best to
multiply the amounts by 100, round to nearest integer, and then do the
arithmetic in integers to avoid floating point equality checks.
Of course, if N is large, this approach is impractical. I should think
any reasonably fast modern PC or Mac could check cases up to N=20 (~ 1
million combinations) fast enough to be usable. If you typically have a
lot more checks than that outstanding, then you'll need a different
approach. There are algorithms for solving integer programming problems
with binary variables (0 or 1 to indicate whether a check has cleared)
and arbitrary coefficients (the transaction amounts). I've no idea how
fast they execute nor do I know of an implementation to point you to.
You might check on-line or in textbooks on integer linear programming
and related subjects.
Rich Sandmeyer
rich.sand at verizon dot net
|