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

244
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
        )
)

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

READ ALSO
Высчитать оставшийся срок в процентах

Высчитать оставшийся срок в процентах

Есть начальная дата, и конечнаяНапример: 30

191
Ускорить выборку из базы opencart 1.5

Ускорить выборку из базы opencart 1.5

на странице выводится по 250 записей

224
Удалить двоеточие запятые т.д. PHP

Удалить двоеточие запятые т.д. PHP

Подскажите как можно удалить из строи все знаки препинания запятые, дефисы, двоеточие и тд

208
mysql_fetch_array() expects parameter 1 to be resource (or mysqli_result), boolean given

mysql_fetch_array() expects parameter 1 to be resource (or mysqli_result), boolean given

Я пытаюсь получить данные из таблицы MySQL, но вылезает одна из этих ошибок:

196