calculate average of all possible combinations of an array

Question

I am having an array value of x numbers, and want output as two arrays that will be closest possible to an average of the main array.

for ex: arr = [1,5,9,14] so avg(arr) = 7.25

now possible combinations = [1+5/2 ; 1+9/2 ; 1+14/2 ; 5+9 /2 ; 9+14/2] so avg of all = [3,5,7.5,7,11.5] the closest possible values are 7 & 7.5 (the output i am expecting)

now the same is possible with arrays of 8 values [1,3,4,6,7,8,5,6] avg = 5; here again, I want to make only two arrays of 4 values each having nearest possible average.

I have tried with the code but still unsure which all math function can help me here:

$temp_data2 = array_map("unserialize", array_unique(array_map("serialize", $temp_data2)));

foreach($temp_data2 as $k => $v){ 
    $diff[abs(10)] = $v; 
}
ksort($diff, SORT_NUMERIC);
$first_pair = current($diff);
print_r($first_pair."::");
print_r($first_pair['combi']);
print_r($temp_data2);

//SECOND PAIR
$temp_data3 =  array();
$temp_data3 = $temp_data2;

$temp_data3 = array_map("unserialize", 
array_unique(array_map("serialize", $temp_data3)));

foreach($temp_data3 as $k => $v){ 
    $diff[abs(10)] = $v; 
}
ksort($diff, SORT_NUMERIC);
$second_pair = current($diff);
print_r($second_pair);

print_r($temp_data3);

In your first example, why isn't `(5 + 14)/2 = 9.5` one of your "possible combinations"? Either that is a typo or I have no idea what you mean by "possible". — John Coleman, Jul 02 '19 at 16:01

score 0 · Answer 1 · answered Jul 03 '19 at 02:55

As far as I understand, we are given an array A of size 2k and we want to find two disjoint subarrays S1, S2 of size k such that the averages of these subarrays is closest to the average of A.

We can measure this deviation with the absolute value:

dev(S1) = abs(avg(S1) - avg(A))
dev(S2) = abs(avg(S2) - avg(A))

And we want to minimize the total deviation

dev(S1) + dev(S2)

The averages are:

avg(A)  = 1/2k * sum_i A_i
avg(S1) = 1/k  * sum_i S1_i
avg(S2) = 1/k  * sum_i S2_i

Since the elements of S2 are those elements of A that are not in S1, we can substitute

avg(S2) = 1/k  * (sum_i A_i - sum_j S_j)

Putting it all together into our objective, we want to minimize

dev(S1) + dev(S2)
  = abs(1/k  * sum_i S1_i - 1/2k * sum_i A_i) + abs(1/k  * (sum_i A_i - sum_j S_j) - 1/2k * sum_i A_i)
  = abs(1/k  * sum_i S1_i - 1/2k * sum_i A_i) + abs(-1/k * sum_j S_j + 1/2k * sum_i A_i)
  = 2 * abs(1/k  * sum_i S1_i - 1/2k * sum_i A_i)

Since k is constant, we can factor it out and get our final objective (without constant scales)

  abs(sum_i S1_i - 1/2 * sum_i A_i)

Therefore, our goal is to pick k elements from A such that their sum is closest to half of the sum of A.

Solving this problem is not easy. Take a look at this question for some ideas. Alternatively, you could use an approximate iterative approach: Start with any set of four numbers. Then, try to replace any number to make the result closer to the desired sum. This is likely to get stuck in local minima, so do not expect to find the best solution in any case.

score 0 · Answer 2 · answered Jul 04 '19 at 12:23

If the two output arrays have the same length then "closest average" is the same as "closest total," because average is the total divided by the number of elements.

Checking all of the possibilities would take too long, because the number of possibilities that must be checked is n!/(n/2)! where n is the number of elements in the original array. For an n of 20 this is over 600 billion.

One way to get something close to the right answer is to sort the array and then loop through it from the largest to the smallest value, putting the next value in the array with the smallest total. Here's an example in JavaScript (because I don't have php set up on this computer). https://jsfiddle.net/3L2qzxwj/

function splitarray(input) {
    input.sort();
    var output = [[],[]];
    var running_totals = [0,0];
    var input_count = input.length;
    var output_count = input_count / 2;
    for (var k = input_count - 1; k >= 0; k--) {
        // if either array is full, put it in the other
        if (output[0].length >= output_count) {
            output[1].push(input[k]);
            running_totals[1] += input[k];
        }
        else if (output[1].length >= output_count) {
            output[0].push(input[k]);
            running_totals[0] += input[k];
        }
        // otherwise put it in the array with the smallest total
        else if (running_totals[0] < running_totals[1]) {
            output[0].push(input[k]);
            running_totals[0] += input[k];
        }
        else {
            output[1].push(input[k]);
            running_totals[1] += input[k];
        }
    }
    return output;
}

calculate average of all possible combinations of an array

2 Answers2