рассчитать среднее значение всех возможных комбинаций массива

Question

У меня есть значение массива x чисел, и я хочу вывести его в виде двух массивов, которые будут максимально приближены к среднему значению основного массива.

для примера: arr = [1,5,9,14], поэтому avg(arr) = 7.25

сейчас possible combinations = [1+5/2 ; 1+9/2 ; 1+14/2 ; 5+9 /2 ; 9+14/2] поэтому avg of all = [3,5,7.5,7,11.5] самые близкие возможные значения 7 и 7,5 (ожидаемый результат)

теперь то же самое возможно с массивами из 8 значений [1,3,4,6,7,8,5,6] avg = 5;и здесь я хочу сделать только два массива по 4 значения, каждое из которых имеет максимально возможное среднее значение.

Я пробовал с кодом, но все еще не уверен, какие математические функции мне могут здесь помочь:

$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);

Answer 1

Если два выходных массива имеют одинаковую длину, то «самое близкое среднее» совпадает с «ближайшим общим», потому что среднее - это общее количество, деленное на количество элементов.

Проверка всех возможностей заняла бы слишком много времени, потому что число проверяемых возможностей равно n! / (N / 2)! где n - количество элементов в исходном массиве. Для n из 20 это более 600 млрд.

Один из способов получить что-то близкое к правильному ответу - отсортировать массив, а затем перебрать его от наибольшего к наименьшему значению, поместив следующее значение в массив с наименьшим общим значением. Вот пример в JavaScript (потому что у меня нет php на этом компьютере). 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;
}

Answer 2

Насколько я понимаю, нам дан массив A размера 2k, и мы хотим найти два непересекающихся подмассива S1, S2 размера k так, чтобы средние значения этих подмассивов были ближе всего к средним A.

Мы можем измерить это отклонение с помощью абсолютного значения:

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

И мы хотим минимизировать общее отклонение

dev(S1) + dev(S2)

Средние значения:

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

Поскольку элементы S2 являются элементами A, которых нет в S1, мы можем заменить

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

Объединяя все это в нашу цель, мы хотим минимизировать

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)

Поскольку k является постоянным, мы можем вычленить его и получить конечную цель (без постоянных масштабов)

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

Поэтому наша цель - выбрать k элементов из A так, чтобы их сумма была ближе к половине суммы A.

Решить эту проблему нелегко. Посмотрите на этот вопрос для некоторых идей. В качестве альтернативы вы можете использовать приблизительный итеративный подход: начать с любого набора из четырех чисел. Затем попытайтесь заменить любое число, чтобы приблизить результат к желаемой сумме. Это может застревать в локальных минимумах, поэтому не ожидайте найти лучшее решение в любом случае.