1

Given a list of transactions like:

A -> 10 to B
B -> 10 to C

The naive way to settle the transaction would be:

C owes 10 to B
B owes 10 to A

But the same transaction could be settled by:

C owes 10 to A

I am representing each transaction as an object:

{
  amount: Number,
  account: Object,
  linkId: Object  
}

So, for a transaction like: A gives 10 to B there would be an object like:

{amount: +10, account: B, linkId: A}

So, if I visualize the transactions then each node could have cycles too. I am trying to find an efficient algorithm but I don't feel confident.

  • Do you care if the solution produces the following: given A owes 10 to B, and C owes 10 to D, then one solution is the obvious, but another solution is that A gives 10 to D and C gives 10 to B. With certain solutions, this kind of thing can occur. – Erik Eidt Nov 29 '16 at 18:30
  • Just from a practical thinking: I don't think you can say C owes 10 to A since the contract between A/B and B/C can be completely different. – qwerty_so Nov 29 '16 at 21:27
4

This looks like the minimize cash flow problem.

Works like this: total credits and debts of each A,B,C... to get a net values for them. Find the two extremes (max at credit and max at debit) and have them transact. The min of the two will have their net go to zero. Now do it again with the ones left over.

It works but sadly this is O(n2).

| improve this answer | |
  • Seems a good approach, but now I have to map my OO code to this procedural one :) – CodeYogi Nov 30 '16 at 2:04
  • 2
    now I have to map my OO code to this procedural one Not at all, now you need to introduce a single object called ClearingHouse, just like the banks (used to) do what you are trying to do. – High Performance Mark Nov 30 '16 at 8:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.