PHP largest whole number from sum of unsorted array

Question

Can someone tell me the best way to find the largest whole number summed from an unsorted array?

e.g.

{0.1, 0.2, 0.9, 0.5}

Largest whole number possible is 1 (0.1 + 0.9).

{0.9, 0.2, 0.5, 0.3, 0.9}

Largest possible is 2 (0.9 + 0.9 + 0.2)

thanks

Update

I've accepted the method that i used but some of the below will be programmatically correct

Answer 1

I would suggest summing up the whole array and then finding the smallest sum with the decimal part equal to that of the whole sum. Unless the numbers have very high precision after the decimal point, whatever the approach to finding the exact number is, this reversal should save a lot of computation.

Also, sorting the array and going greedy from the smallest numbers might yield nice results. However, the optimal solution is very dependent on the nature of the initial set. Could you provide any closer specifications on what kind of numbers you expect?

Answer 2

This is a great problem to think about. Off the top of my head, this is the pseudocode I'd use:

1. A = array of elements.
2. A' = sorted array of elements.
3. S = sum of all elements.
4. While A' isn't empty:
   1. V = integer portion of S.
   2. R = remainder of S = S - floor(S)
   3. Make a temporary copy of A', X.
   4. Iterate from largest to smallest values of X as X[i]:
      1. If X[i] < R, subtract X[i] from R. Remove X[i] from X.
      2. If R == 0, we've found the solution. V is the whole number, X contains the addends. STOP.
   5. If X is empty, there is no solution. STOP.
   6. Reduce S by the largest value in A'. S = S - Max(A'). Remove Max(A') from A'.
5. Go back to step #4.

Of course, I had to see if this would actually work. Here's the (very messy, throw-away quality) code I wrote to test it:

<?php
$AA = $A = array(0.1, 0.2, 0.9, 0.5);

bcscale(8);

sort($AA, SORT_NUMERIC);
echo 'A = ' . implode(', ', $A), PHP_EOL;
echo 'A\' = ' . implode(', ', $AA), PHP_EOL;

$S = array_sum($AA);
echo 'S = ' . $S, PHP_EOL;

while (count($AA)) {
    $V = floor($S);
    echo 'V = ' . $V, PHP_EOL;

    $R = bcsub($S, $V);
    echo 'R = ' . $R, PHP_EOL;

    $X = $AA;
    $XX = array();

    // Look for the largest value that is less than or equal to R.
    for ($i = count($X) - 1; $i >= 0; $i--) {
        echo 'X[i] = ' . $X[$i] . ', R = ' . $R, PHP_EOL;
        $c = bccomp($X[$i], $R);
        if ($c > 0) {
            continue;
        }
        $XX[] = $X[$i];
        $R = bcsub($R, $X[$i]);
        unset($X[$i]);

        if (bccomp($R, '0', strlen($R)) == 0) {
            echo 'Largest whole number sum: ' . $V, PHP_EOL;  
            echo 'Elements: ' . implode(', ', $X), PHP_EOL;   
            break 2;
        }
    }

    if (count($X) == 0) {
        echo 'No sums to a whole number are possible.', PHP_EOL;
        break;
    }

    $t = array_pop($AA);
    $S = bcsub($S, $t);
}

echo 'S = ' . $S, PHP_EOL;
?>

It's an ugly O(N^2) algorithm, but it should be correct. Can anyone see an initial starting array where this would fail?

For fun, I tried with an array of 50 elements, replacing the first line with these lines:

$A = array();
for ($i = 0; $i < 50; $i++) {
    $A[] = mt_rand(1, 99) / 100.0;
}
$AA = $A;

At a glance, it looks right - I'll leave verification up to someone else ;)

Answer 3

The bulk of this code is for getting the permutations of an array. I'm sure it can be optimized, but this is calculating 3 arrays with lengths of 4, 5 and 6 in 45ms on a quad core single Xeon server. Jumps to about 220ms when I add a 4th array with 7 decimals and a whopping 2 seconds if I add a 5th with 8.

Basically, all this does is get all of the permutations of the array containing the floats, adds each one together key by key, and if a the sum is a whole number larger than the current whole number, updates that number.. Eventually returning the largest possible number.

$set1 = array(0.1, 0.2, 0.9, 0.5);
$set2 = array(0.9, 0.2, 0.5, 0.3, 0.9);
$set3 = array(0.9, 0.2, 0.5, 0.3, 0.9, 0.4);

function largestWholeNumber($decimals){
    echo "Calculating largest whole number for decimal set '"
    . implode(",", $decimals)
    . "'<br />";
    $perms = perms($decimals);
    $answer = 0;
    foreach($perms as $dec_array){
        $current_guess = 0;
        foreach($dec_array as $dec){
            $current_guess += $dec;
            if (!preg_match("/[^0-9]+/", $current_guess)){
                if ($answer < $current_guess){
                    $answer = $current_guess;
                    echo "New whole number found " 
                    ."'$answer'"
                    ." with permutation: <br />";
                    print_r($dec_array);
                    echo "<br />";
                }
            }
        }
    }
    echo "Result: $answer<br /><br />";
    return $answer;
}

function factorial($int){
if($int < 2) {
       return 1;
}

for($f = 2; $int-1 > 1; $f *= $int--);

return $f;
}


function perms($arr) {
    $p = array();
    for ($i=0; $i < factorial(count($arr)); $i++) {
        $p[] = perm($arr, $i);
    }
    return $p;
}


function perm($arr, $nth = null) {

    if ($nth === null) {
        return perms($arr);
    }

    $result = array();
    $length = count($arr);

    while ($length--) {
        $f = factorial($length);
        $p = floor($nth / $f);
        $result[] = $arr[$p];
        array_delete_by_key($arr, $p);
        $nth -= $p * $f;
    }

    $result = array_merge($result,$arr);
    return $result;
}
function array_delete_by_key(&$array, $delete_key, $use_old_keys = FALSE) {

    unset($array[$delete_key]);

    if(!$use_old_keys) {
        $array = array_values($array);
    }

    return TRUE;
}

largestWholeNumber($set1); // 1
largestWholeNumber($set2); // 2
largestWholeNumber($set3); // 3

Credit to the array permutation function goes to dirk dot avery a t gmail at http://php.net/manual/en/function.shuffle.php

Answer 4

OK thinking about it.

$sum = array_sum($arr);
$floor_sum = floor($sum);
if ($sum = $floor_sum){
return $sum
}else{

for ($i = 0; $i < sizeof($arr); $i++){
  if ($sum - $arr[$i] = $floor_sum){
     return $sum - $arr[i];
  }else{
    for ($x = 0; $x < sizeof($arr)- 1; $x++){
      if ($x != $i){
        if ($sum - $arr[$i] - $arr[$x] = $floor_sum){
         return $sum - $arr[$i] - $arr[$x];
        }else {
            //Iterate more times
        }
      }
    }
  }
}

}

i have the above but there must be an easier way to do it?

Answer 5

I have not written the code for this, but the psuedo code is below. The general idea is that you compute combinations (x choose y... http://en.wikipedia.org/wiki/Combination ) and then sum each of those combinations. You iterate over this for the length of the array, and then take your max.

I am also sure there are optimizations regarding being greedy and short-circuiting this loop.

$len = count($decimals);
$maxVals = array();

for( $choose = $len; $choose > 1; $choose-- ) {
    // get $decimals choose $choose

    // loop and sum each choose array, checking for an integer sum

    // store max if exists
}

return sum($maxVals);

Answer 6

something like this?

 $array=array(0.1, 0.2, 0.9, 0.5);
 arsort($array);
 while($highest=array_shift($array)){
   foreach($array as $val){
    $thisval=($highest+val);
    if(round($thisval)==($thisval)){
     return $thisval;
   }
 }
}

EDIT: @Felix Kling you are absolutely right, added a while loop