StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>if A, B and C each owe $1 to each of D, E and F, the "list" or "central bank" solution creates five transactions (e.g. A,B,C -$3-> D, D -$3-> E,F) whereas the naive solution results in nine transactions. However, if A owes only to D, B only to E and C only to F the central bank solution creates still five transactions (A,B,C -$1-> D, D -$1-> E,F) whereas the best solution needs only three (A -$1-> D, B -$1-> E, C -$1-> F). This shows that the "list" or "central bank" solution is not optimal in general.</p> <p>The following greedy algorithm can be used to create better solutions to the problem, but they are not always optimal. Let "debt[i,j]" denote the amount of money person i owes to person j; initially this array is initialized according to the situation.</p> <pre><code>repeat until last: find any (i, j) such that |K = {k : debt[i,k] > 0 and debt[j,k] > 0}| >= 2 if such (i, j) found: // transfer the loans from i to j total = 0 for all k in K: debt[j,k] += debt[i,k] total += debt[i,k] debt[i,k] = 0 person i pays 'total' to person j else: last for every i, j in N: if (debt[i,j] > 0) person i pays debt[i,j] to person j </code></pre> <p>They key of this algorithm is the observation that if both A and B owe money to both C and D, instead of the four transactions required for direct payments, B can pay the net debt to A who can take care of paying back both A's and B's loans.</p> <p>To see how this algorithm works, consider the case where A, B and C each own $1 to each of D, E, F:</p> <ol> <li>A transfers A's debts to B, and pays $3 to B (one transaction)</li> <li>B transfers B's debts to C, and pays $6 to C (one transaction)</li> <li>Only C has debts any more; C pays $3 to D, E and F each (three transactions)</li> </ol> <p>But in the case where A owes D, B owes E and C owes F, the algorithm falls through immediately to the payment loop, resulting in the optimal number of transactions (only three) instead of five transactions which would result from the "central bank" approach.</p> <p>An example of non-optimality is where A owes to D and E, B owes to E and F and C owes to F and D (assume $1 for every debt). The algorithm fails to consolidate the loans because no two payers share two common payees. This could be fixed by changing ">= 2" on the second line to ">= 1", but then the algorithm would most likely become very sensitive to the order in which the debts are collateralized.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload