language agnostic - What algorithm to use to determine minimum number of actions required to get the system to "Zero" state? -

this kind of more generic question, isn't language-specific. more idea , algorithm use.

the system follows:

it registers small loans between groups of friends. alice , bill going lunch, bill's card isn't working, alice pays meal, $10.
next day bill , charles meet each other on railway station, chales has no money ticket, bill buys him one, $5. later day alice borrows $5 charles , $1 bill buy friend gift.

now, assuming registered transactions in system, looks this:

alice -> bill $10 bill -> alice $1 bill -> charles $5 charles -> alice $5 

so, now, thing needs done bill giving alice $4 (he gave $1 , charlie transferred $5 alice alredy) , they're @ initial state.

if scale many diffrent people, having multiple transaction, best algorithm little transactions possible?

this looks job double entry accounting concept with.

your transactions structured 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 have it. @ each transaction, credit 1 ledger account , debit balance zero. @ at end, work out minimal number transactions applied each account return zero.

for simple case, it's simple $4 transfer bill alice. need reduce @ least 1 account (but preferably two) 0 every transaction added. let's had 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 transactions needed be:

bill     -> alice   $4       0     1-       1        0 bill     -> charles $1       0     0        0        0 

---

unfortunately, there states simple greedy strategy not generate best solution (kudos j_random_hacker pointing out). 1 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, reversed in 4 moves (since 4 moves took there) but, if choose first move unwisely (edie->bill $2), 5 minimum you'll away with.

you can solve particular problem following rules:

• (1) if can wipe out 2 balances, it.
• (2) otherwise if can wipe out 1 balance , set wipe out 2 in next move, it.
• (3) otherwise, wipe out 1 balance.

that result in following sequence:

• (a) [1] not applicable, [2] can achieved alan->bill $5.
• (b) [1] can done chas->bill $20.
• (c) , (d), similar reasoning doug, edie , fred, 4 total moves.

however, works because of small number of possibilities. number of people rises , group inter-relations becomes more complex, you'll need exhaustive search find minimum number of moves required (basically rules 1, 2 , 3 above expanded handle more depth).

i think required give smallest number of transactions in circumstances. however, may that's not required best answer (best, in case, meaning maximum "bang per buck"). may basic 1/2/3 rule set give good-enough answer purposes.