3
\$\begingroup\$

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?

\$\endgroup\$
4
  • \$\begingroup\$ When you say the best way do you mean the least number of payments? \$\endgroup\$ – bumperbox Mar 12 '14 at 12:00
  • \$\begingroup\$ 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. \$\endgroup\$ – harryg Mar 12 '14 at 12:06
  • \$\begingroup\$ 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. \$\endgroup\$ – bumperbox Mar 12 '14 at 12:35
  • \$\begingroup\$ 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. \$\endgroup\$ – harryg Mar 13 '14 at 8:58
2
\$\begingroup\$

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;
}
\$\endgroup\$

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.