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?