php - Distribute associative array elements into groups with a maximum sum per group

233

I need to split my associative array into bunches of not greater than 50 in each bunch. Multiple elements may be pushed into a given group to ensure that a group reaches 50 before starting a new group.

Sample input:

$array = [
    '5' => 142,
    '2' => 57,
    '18' => 37
];

Desired result:

[
    ['5' => 50],
    ['5' => 50],
    ['5' => 42, '2' => 8],
    ['2' => 49, '18' => 1],
    ['18' => 36],
];

Answer

Solution:

just mind games

$line = [];
// Invert array
foreach($arr as $k=>$v) {
   $line = array_merge($line, array_fill(0, $v, $k));
}
// Split and count occurrences
$res = array_map('array_count_values', array_chunk($line, 50));
print_r($res);

947

Answer

Solution:

You could try something like this :

$total = [] ; $ckey = 0 ; 
foreach ($array as $key => $value) {
    while ($value) {
        $cursum = isset($total[$ckey]) ? array_sum($total[$ckey]) : 0 ;
        if ($cursum == 50) $ckey++ ;

        if ($value + $cursum > 50) $add = 50 - $cursum ;
        else  $add = $value ;

        $total[$ckey][$key] = $add ;
        $value -= $add ;
    }
}
print_r($total) ;

Outputs :

Array (
    [0] => Array (
            [5] => 50
        )

    [1] => Array (
            [5] => 50
        )

    [2] => Array (
            [5] => 42
            [2] => 8
        )

    [3] => Array (
            [2] => 49
            [18] => 1
        )

    [4] => Array (
            [18] => 36
        )
)

130

Answer

Solution:

My train of thought for this task aligns with @Syscall's "push & consume" approach.

Iterate the input array to access the keys and values.
Use an inner loop to repeatedly process the current value until it is fully consumed by subtraction. Only break the loop upon the value being reduced to zero.
With each pass of the inner loop:
- Calculate the current total of all values in the group, then
- Find the lesser integer value between how much room is left in the group and how much is left in the value; push that integer into the group with the current key; then subtract that integer from the current value, then
- Increment the group key if the current group has reach its limit
Repeat until all input elements are reduced to zero.

Code: (Demo)

$groupLimit = 50;  // declare as a variable to avoid "magic numbers" in code

$result = [];
$groupKey = 0; 
foreach ($array as $key => $value) {
    while ($value) {
        $sum = array_sum($result[$groupKey] ?? []);                           // get group sum
        $value -= $result[$groupKey][$key] = min($groupLimit - $sum, $value); // push key with limited value; decrease value
        $groupKey += ($sum + $result[$groupKey][$key] === $groupLimit);       // only increment group key if at $groupLimit
    }
}
var_export($result);

People are also looking for solutions to the problem: javascript - Sending the timing from the page load to the last occurrence of a button click?

Source

Didn't find the answer?

Our community is visited by hundreds of web development professionals every day. Ask your question and get a quick answer for free.

Ask a Question