# Can this PHP code to settle up payments be improved?

I've made a function that takes an array of amounts owed by each user_id and works out the best way to square everyone up. The input array would look something like this, but may consist of 1 or more "users" who all owe (or are owed) money between each other:

//the owings should sum to 0.
$owings = array( 1 => -1.72, //user 1 owes -1.72 2 => -5.78, 3 => 7.5, );  And here is my function: /** * Calculate the most efficient way to settle up a group of payments * * @param array$owings
*/
function settleUp($owings){$reimbursments = array();
$payment = 0.11;$i = 1;
while ( $payment > 0.1 ||$payment < -0.1 ){
$min = 0;$max = 0;
foreach ($owings as$id => $owing){ if ($owing < $min) {$min = $owing;$min_id = $id; } if ($owing > $max) {$max = $owing;$max_id = $id; } }$payment = -$min >$max ? -$max :$min;

if ($payment !== 0) {$reimbursments[] = array(
'from'      => $max_id, 'to' =>$min_id,
'payment'   => -$payment, );$owings[$max_id] +=$payment;
$owings[$min_id] -= $payment; }$i++;
}
return $reimbursments; }  The result looks like this: //print_r(settleUp($owings));
Array
(
[0] => Array
(
[from] => 3
[to] => 2
[payment] => 5.78
)
[1] => Array
(
[from] => 3
[to] => 1
[payment] => 1.72
)
)


Currently I use a while loop that iterates until the net balance owed is close to 0. Is there a better way of doing this? Perhaps using a recursive function?

• When you say the best way do you mean the least number of payments? – bumperbox Mar 12 '14 at 12:00
• Yes, the most efficient way for a group of people to all square up. E.g If Tim owes Sue £20 and Sue owes Tim £5 it would be better for Tim just to pay Sue £15 than for them both to pay each other the amount they owe. This is a simple example but gets more complicated with more people. – harryg Mar 12 '14 at 12:06
• I wasn't sure if you wanted to try all the possible combinations and see which results in the minimum number of payments or not. – bumperbox Mar 12 '14 at 12:35
• I'm pretty sure my method should always give the minimum number of payments but I wanted to verify this and see if there was a more efficient or elegant way of doing it. You suggestions are helpful though. – harryg Mar 13 '14 at 8:58

Well if you want to split hairs, you could do a couple of minor changes (commented below)

Honestly, I can't see any advantage in making it recursive, it works fine as it is

function settleUp($owings){$reimbursments = array();

// $i is never used //$payment = 0.11; $i = 1; // by using a do/while loop you don't need to assign$payment to a random value to being the loop
do {
$min = 0;$max = 0;
foreach ($owings as$id => $owing){ if ($owing < $min) {$min = $owing;$min_id = $id; } if ($owing > $max) {$max = $owing;$max_id = $id; } }$payment = -$min >$max ? -$max :$min;

if ($payment !== 0) {$reimbursments[] = array(
'from'      => $max_id, 'to' =>$min_id,
'payment'   => -$payment, );$owings[$max_id] +=$payment;
$owings[$min_id] -= $payment; } //$i++;
} while ( $payment > 0.1 ||$payment < -0.1 );

return \$reimbursments;
}