Splitting Up: An algorithm

In a previous post, we considered an algorithm for settling accounts between friends who are splitting up a dinner bill.

At the end of the "pre-processing" step, we have a list of names (say ['p1', 'p2', 'p4', 'p3'])and a list of corresponding net contributions (x = [2, 7, -4, -5]), which add to zero.

We now consider the problem of generating the transaction list. The first thing to do is to sort contributions from highest to lowest.

Here, we would have, [p2, 7], [p1, 2], [p4, -4], and [p3, -5].

We now consider a transaction between the first and last members of the list. Once consummated, one of the members will be "settled", and hence out of reckoning for the rest of the calculation.

In this case, p3 pays p2 $5, and is out! (Transaction 1)

We then re-sort the remaining members to get, [p2, 2], [p1, 2], and [p4, -4].

Again we consider a transaction between the first and last members of the list.

In this case, p4 pays p2 $2, and is p2 is done! (Transaction 2)

We then re-sort the remaining members to get, [p1, 2], and [p4, -2], which can be settled by:

In this case, p4 pays p1 $2, and everyone is done.

It is easy to see that since at least one member drops out of contention during each transaction, we will need N-1 transactions at most.

We can write this up as an algorithm:

1. sort xi. set n = N.
2. consider transaction between x1 and xn.
3. if x1>abs(xn), transaction = pn pays $abs(xn) to p1, and is removed from the list. n = n - 1
4. elseif x1
5. elsife x1=abs(xn), transaction = pn pays x1 to p1, and both p1 and pn are removed from the list. n = n - 2
6. Sort remaining xi.
7. Repeat steps 3 through 6 until n = 0.