The README describes the settlement output as optimized, but the greedy matching can suggest more transfers than are needed.
Example, as net balances in paise:
U1 +900 U2 +400 U0 -200 U3 -400 U4 -700
GET /groups/{id}/settlements returns 4 transfers:
U4 -> U1 700
U3 -> U1 200
U3 -> U2 200
U0 -> U2 200
Only 3 are needed, because {U1, U4, U0} and {U2, U3} each add up to zero on their own:
U4 -> U1 700
U0 -> U1 200
U3 -> U2 400
I found this by comparing the current output with a brute-force minimum on random small groups, and it shows up regularly, so it is not a one-off. I reproduced the example above through the real API by creating expenses that produce those balances.
Worth knowing: the minimum number of transfers is NP-hard in general, so a perfect answer is not the goal. For the group sizes this app is aimed at (a handful of people), a cheap improvement is to first pull out zero-sum subsets, then run the existing greedy pass on whatever is left.
Small related note: the README says to repeatedly match "the largest remaining debtor with the largest remaining creditor", but SettlementService.get_group_settlements sorts both lists once and walks them in that order, so after a partial payment it does not re-pick the largest. Either the code or the README wording should be aligned.
The README describes the settlement output as optimized, but the greedy matching can suggest more transfers than are needed.
Example, as net balances in paise:
GET /groups/{id}/settlementsreturns 4 transfers:Only 3 are needed, because {U1, U4, U0} and {U2, U3} each add up to zero on their own:
I found this by comparing the current output with a brute-force minimum on random small groups, and it shows up regularly, so it is not a one-off. I reproduced the example above through the real API by creating expenses that produce those balances.
Worth knowing: the minimum number of transfers is NP-hard in general, so a perfect answer is not the goal. For the group sizes this app is aimed at (a handful of people), a cheap improvement is to first pull out zero-sum subsets, then run the existing greedy pass on whatever is left.
Small related note: the README says to repeatedly match "the largest remaining debtor with the largest remaining creditor", but
SettlementService.get_group_settlementssorts both lists once and walks them in that order, so after a partial payment it does not re-pick the largest. Either the code or the README wording should be aligned.