What algorithm to use to determine minimum number of actions required to get the system to "Zero" state?
Solution 1:
This actually looks like a job that the double entry accounting concept could help with.
Your transactions could be structured as bookkeeping entries thus:
Alice Bill Charles Balance
Alice -> Bill $10 10 10- 0 0
Bill -> Alice $1 9 9- 0 0
Bill -> Charles $5 9 4- 5- 0
Charles -> Alice $5 4 4- 0 0
And there you have it. At each transaction, you credit one ledger account and debit another so that the balance is always zero. At at the end, you simply work out the minimal number transactions to be applied to each account to return it to zero.
For this simple case, it's a simple $4 transfer from Bill to Alice. What you need to do is to reduce at least one account (but preferably two) to zero for every transaction added. Let's say you had the more complicated:
Alice Bill Charles Balance
Alice -> Bill $10 10 10- 0 0
Bill -> Alice $1 9 9- 0 0
Bill -> Charles $5 9 4- 5- 0
Charles -> Alice $5 4 4- 0 0
Charles -> Bill $1 4 5- 1 0
Then the transactions needed would be:
Bill -> Alice $4 0 1- 1 0
Bill -> Charles $1 0 0 0 0
Unfortunately, there are some states where this simple greedy strategy does not generate the best solution (kudos to j_random_hacker for pointing this out). One example is:
Alan Bill Chas Doug Edie Fred Bal
Bill->Alan $5 5- 5 0 0 0 0 0
Bill->Chas $20 5- 25 20- 0 0 0 0
Doug->Edie $2 5- 25 20- 2 2- 0 0
Doug->Fred $1 5- 25 20- 3 2- 1- 0
Clearly, this could be reversed in four moves (since four moves is all it took to get there) but, if you choose your first move unwisely (Edie->Bill $2), five is the minimum you'll get away with.
You can solve this particular problem with the following rules:
- (1) if you can wipe out two balances, do it.
- (2) otherwise if you can wipe out one balance and set yourself up to wipe out two in the next move, do it.
- (3) otherwise, wipe out any one balance.
That would result in the following sequence:
- (a) [1] not applicable, [2] can be achieved with
Alan->Bill $5. - (b) [1] can be done with
Chas->Bill $20. - (c) and (d), similar reasoning with Doug, Edie and Fred, for four total moves.
However, that works simply because of the small number of possibilities. As the number of people rises and the group inter-relations becomes more complex, you'll most likely need an exhaustive search to find the minimum number of moves required (basically the rules 1, 2 and 3 above but expanded to handle more depth).
I think that is what will be required to give you the smallest number of transactions in all circumstances. However, it may be that that's not required for the best answer (best, in this case, meaning maximum "bang per buck"). It may be that even the basic 1/2/3 rule set will give you a good-enough answer for your purposes.
Solution 2:
Intuitively, this sounds like an NP-complete problem (it reduces to a problem very like bin packing), however the following algorithm (a modified form of bin packing) should be pretty good (no time for a proof, sorry).
-
Net out everyone's positions, i.e. from your example above:
Alice = $4 Bill = $-4 Charles = $0
Sort all net creditors from highest to lowest, and all debtors from lowest to highest, then match by iterating over the lists.
At some point you might need to split a person's debts to net everything out - here it is probably best to split into the biggest chunks possible (i.e. into the bins with the most remaining space first).
This will take something like O(n log n) (again, proper proof needed).
See the Partition Problem and Bin Packing for more information (the former is a very similar problem, and if you limit yourself to fixed precision transactions, then it is equivalent - proof needed of course).
Solution 3:
I have created an Android app which solves this problem. You can input expenses during the trip, it even recommends you "who should pay next". At the end it calculates "who should send how much to whom". My algorithm calculates minimum required number of transactions and you can setup "transaction tolerance" which can reduce transactions even further (you don't care about $1 transactions) Try it out, it's called Settle Up:
https://market.android.com/details?id=cz.destil.settleup
Description of my algorithm:
I have basic algorithm which solves the problem with n-1 transactions, but it's not optimal. It works like this: From payments, I compute balance for each member. Balance is what he paid minus what he should pay. I sort members according to balance increasingly. Then I always take the poorest and richest and transaction is made. At least one of them ends up with zero balance and is excluded from further calculations. With this, number of transactions cannot be worse than n-1. It also minimizes amount of money in transactions. But it's not optimal, because it doesn't detect subgroups which can settle up internally.
Finding subgroups which can settle up internally is hard. I solve it by generating all combinations of members and checking if sum of balances in subgroup equals zero. I start with 2-pairs, then 3-pairs ... (n-1)pairs. Implementations of combination generators are available. When I find a subgroup, I calculate transactions in the subgroup using basic algorithm described above. For every found subgroup, one transaction is spared.
The solution is optimal, but complexity increases to O(n!). This looks terrible but the trick is there will be just small number of members in reality. I have tested it on Nexus One (1 Ghz procesor) and the results are: until 10 members: <100 ms, 15 members: 1 s, 18 members: 8 s, 20 members: 55 s. So until 18 members the execution time is fine. Workaround for >15 members can be to use just the basic algorithm (it's fast and correct, but not optimal).
Source code:
Source code is available inside a report about algorithm written in Czech. Source code is at the end and it's in English:
http://www.settleup.info/files/master-thesis-david-vavra.pdf