A pays 12.34 (B, C, & D owe A 3.085) B pays 23.45 (A, C, & D owe B 5.8625) C pays 45.67 (A, B, & D owe C 11.4175) D pays 34.56 (A, B, & C owe D 8.64)
| b -> a 3.085 | ||
| a -> b 5.8625 | ||
| A pays B 2.7775 | ||
| c -> a 3.085 | c -> b 5.8625 | |
| a -> c 11.4175 | b -> c 11.4175 | |
| A pays C 8.3325 | B pays C 5.555 | |
| d -> a 3.085 | d -> b 5.8625 | d -> c 11.4175 |
| a -> d 8.64 | b -> d 8.64 | c -> d 8.64 |
| A pays D 5.555 | B pays D 2.7775 | D pays C 2.7775 |
A pays B 2.7775, but since B is paying C 5.555 then it’s fewer steps to have A pay C the 2.7775 and now B only has to pay C 2.7775.
If we do that, then now A doesn’t have to pay B anymore, and instead pays C 11.11. Let’s do it again – A is paying D 5.555 while D is paying C 2.7775. So let’s have A pay another 2.7775 to C and reduce D’s credit by that amount, leaving us with:
| A & B are settled | ||
| A pays C 13.8875 | B pays C 2.7775 | |
| A pays D 2.7775 | B pays D 2.7775 | D & C are settled |
Now, assuming we trust this group (and we do), we can do some debt shuffling to reduce the total number of payments even further. Let’s try to have A trade B’s debt to C in exchange for A’s debt to D. Start:
| A & B are settled | ||
| A pays C 13.8875 + 2.7775 | B pays C 2.7775 - 2.7775 | |
| A pays D 2.7775 - 2.7775 | B pays D 2.7775 + 2.7775 | D & C are settled |
End:
| A & B are settled | ||
| A pays C 16.665 | B & C are settled | |
| A & D are settled | B pays D 5.555 | D & C are settled |
116.02 /4 29.005 per person
A (- 29.005 12.34) 16.665 B (- 29.005 23.45) 5.555 C (- 29.005 45.67) -16.6650 D (- 29.005 34.56) -5.5550
A pays 24.65 (B & C owe A 8.2166666667) B pays 19.02 (A & C owe B 6.34) C pays 25.05 (A & B owe B 8.35)
(+ 24.65 19.02 25.05)68.72 (/ 68.72 3)22.906666666666666
A (- 22.906666666666666 24.65) -1.7433333333333323 B (- 22.906666666666666 19.02) 3.8866666666666667 C (- 22.906666666666666 25.05) -2.1433333333333344
A pays 24.65 (B & C & D owe A 6.1625) B pays 19.02 (A & C & D owe B 4.755) C pays 25.05 (A & B & D owe C 6.2625) D pays 20.00 (A & B & C owe D 5)
(+ 24.65 19.02 25.05 20)88.72 (/ 88.72 4)22.18
A (- 22.18 24.65) -2.469999999999999 B (- 22.18 19.02) 3.16 C (- 22.18 25.05) -2.870000000000001 D (- 22.18 20.00) 2.1799999999999997
| A pays B (- 4.755 6.1625) | |||
| A pays C (- 6.2625 6.1625) | B pays C (- 6.2625 4.755) | ||
| A pays D (- 5 6.1625) | B pays D (- 5 4.755) | C pays D (- 5 6.2625) | |
| A pays B -1.4075 + .1 | B pays A - .1 | ||
| A pays C 0.1000 - .1 | B pays C 1.5075 + .1 | ||
| A pays D -1.1625 | B pays D 0.2450 | C pays D -1.2625 | |
| (+ -1.1625 -1.4075 .1) -2.47 | (+ 1.4075 1.7525) 3.16 | (+ -.1 -1.5075 -1.2625) -2.87 | (+ 1.1625 -0.2450 1.2625) 2.18 |
| A pays B -1.3075 – | B pays A ++ | ||
| A & C are settled | B pays C 1.6075 | ||
| A pays D -1.1625 ++ | B pays D 0.2450 – | C pays D -1.2625 | |
| (+ -1.3075 -1.1625) -2.47 | (+ 1.3075 1.6075 .2450) 3.16 | (+ -1.6075 -1.2625) -2.87 | |
| A pays B -1.5525 – | B pays A ++ | ||
| A & C are settled | B pays C 1.6075 – | ||
| A pays D -0.9175 ++ | B & D are settled | C pays D -1.2625 – | +- |
| (+ -1.5525 -.9175) -2.47 | (+ 1.5525 1.6075) 3.16 | (+ -1.6075 -1.2625) -2.87 | (+ .9175 1.2625) 2.18 |
If we stopped here, we’d have: B pays A 1.5525 ~ 1.55 B pays C 1.6075 ~ 1.61 D pays A 0.9175 ~ 0.92 D pays C 1.2625 ~ 1.27 Precision loss adds 1c to money moved
B->C -1.6075 B & C are settled B->A +1.6075 B’s debt to A increases A->D +1.6075 A’s debt to D increases (previous D owed A, but this is enough to flip it so now A owes D) D->C -1.6075 D’s debt to C increases
| A pays B -3.16 | B pays A | ||
| A & C are settled | B & C are settled | ||
| A pays D 0.69 | B & D are settled | C pays D -2.87 | |
| (+ -3.16 .69) -2.47 | (+ 3.16) 3.16 | (+ -2.87) -2.87 | (+ -.69 2.87) 2.18 |
Now we’ve got: B pays A 3.16 A pays D 0.69 D pays C 2.87
Going back to the start,
A (- 22.18 24.65) -2.469999999999999 B (- 22.18 19.02) 3.16 C (- 22.18 25.05) -2.870000000000001 D (- 22.18 20.00) 2.1799999999999997
If the desired output is something like:
B pays A 3.16 A pays D 0.69 D pays C 2.87
Then:
- Sort people by debt to the group descending
| B | 3.1600 |
| D | 2.1800 |
| A | -2.4700 |
| C | -2.8700 |
- Have the person with the most debt pay it all to the person with the most credit
| B | 3.1600 | - 3.16 to C | 0 |
| D | 2.1800 | 2.1800 | |
| A | -2.4700 | -2.4700 | |
| C | -2.8700 | + 3.16 from B | 0.29 |
- Repeat
| D | 2.1800 | - 2.18 to A | 0 |
| C | 0.29 | 0.29 | |
| B | 0 | 0 | |
| A | -2.4700 | + 2.18 from D | -0.29 |
- Repeat
| C | 0.29 | - 0.29 to A | 0 |
| D | 0 | 0 | |
| B | 0 | 0 | |
| A | -0.29 | + 0.29 from C | 0 |
- Done!
This resulted in: B pays C 3.16 D pays A 2.18 C pays A 0.29
Which results in exactly the same final balances per person as the manual solution above: B pays A 3.16 A pays D 0.69 D pays C 2.87
Since in both cases: A is up 2.47 (man. 3.16 - 0.69, algo. 2.18 + 0.29) B is down 3.16 (man. 3.16, algo. 3.16) C is up 2.87 (man. 2.87, algo. 3.16 - 0.29) D is down 2.18 (man. 2.87 - 0.69, algo. 2.18)
And these figures equal each person’s diff from the group average seen above: A (- 22.18 24.65) -2.469999999999999 B (- 22.18 19.02) 3.16 C (- 22.18 25.05) -2.870000000000001 D (- 22.18 20.00) 2.1799999999999997
A (- 22.9067 24.65) -1.7433 B (- 22.9067 19.02) 3.8867 C (- 22.9067 25.05) -2.1433
- Sort people by debt to the group descending
| B | 3.8867 |
| A | -1.7433 |
| C | -2.1433 |
- Have the person with the most debt pay it all to the person with the most credit
| B | 3.8867 | -3.8867 to C | 0 |
| A | -1.7433 | -1.7433 | |
| C | -2.1433 | +3.8867 from B | 1.7434 |
- Repeat
| C | 1.7434 | 1.7434 to A |
| A | -1.7433 | Yep it works |