Разделение массива на равные части (при этом каждая часть с другой по сумме примерно совпадает)

243

16 июня 2018, 21:30

Всем привет. За основу взят алгоритм O(n log n) https://en.wikipedia.org/wiki/Partition_problem Только проблема в том, что конструкция не жизнеспособна в случае если на вход может приходить разное кол-во колонок

<?php
function partList($arr, $groups) {
$a = [];
$b = [];
$c = [];
$arrCount = count($arr);
$result = [];
sort($arr, SORT_NUMERIC);
for ($i = 0; $i < $arrCount; $i++) {
    if (array_sum($a) < array_sum($b)) {
        $a[] = $arr[$i];
    } else if (array_sum($b) < array_sum($c)){
        $b[] = $arr[$i];
    } else {
        $c[] = $arr[$i];
    }
}

var_dump($a, $b, $c);
}

$arr = [1,2,4,7,1,6,2,8];
partList($arr, 3);

Т.е. не понимаю что дальше делать с groups, как должен выглядеть встроенный в for еще один цикл который примет кол-во груп и разобьет на них чтобы не приходилось каждый раз расписывать условия?

http://sandbox.onlinephpfunctions.com/code/a823a059aa787339dd823cc1b3e23b9879b2b99a

Answer 1

Как-то так:

function partList($arr, $groups = 3){
    $newArray = array_fill(0, $groups, []);
    rsort($arr, SORT_NUMERIC);
    foreach ($arr as $value){
        usort($newArray, function($one, $thwo){
            return array_sum($one) > array_sum($thwo);
        });
        $newArray[0][] = $value;     
    }
    return $newArray;
}
$arr = [1,2,4,7,1,6,2,8];
print_r(partList($arr));

Вывод:

Array
(
    [0] => Array
        (
            [0] => 7
            [1] => 2
            [2] => 1
            [3] => 1
        )
    [1] => Array
        (
            [0] => 8
            [1] => 2
        )
    [2] => Array
        (
            [0] => 6
            [1] => 4
        )
)

Ну это конечно еще не совсем точно будет считать, если будут злобные числа...
В теории, если будут числа соответствовать суммам, посчитает правильно, а так, будет наглядные числа...