CODEWITHSUNDEEP
phparraysgroupingmathematical-optimizationinteger-arithmetic
Anurag
Anurag

Reputation: 555

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

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],
];

Upvotes: 1

Views: 190

Answers (3)

Syscall
Syscall

Reputation: 19764

To create an array where the sum of each entry would not exceed a given amount, you can use an iterative approach.

Let's start with an empty array and a variable representing the working index of that array. As we go through the input array, we add the maximum possible remaining quantity to the new array. If we reach the limit, we increment the index variable. And we continue as long as the input array has not been completely browsed.

Code:

const MAX_SUM = 50;
$total  = []; // Store the new data
$curKey = 0;  // Store the current key of $total array.
foreach ($array as $key => $value) {
    while ($value) {
        // Get the current sum for the current key:
        $curSum = array_sum($total[$curKey] ?? []);

        // If the max was reached, we can go to the next key:
        if ($curSum == MAX_SUM) $curKey++;

        // Now, compute if the value to add (max to reach 50);
        $add = $value + $curSum > MAX_SUM // If above,
            ? MAX_SUM - $curSum           // got only the difference,
            : $value;                     // else, use the full value.

        // Add the value
        $total[$curKey][$key] = $add;

        // Finally, remove what we added just before.
        $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
        )
)

See also a the nice answer of @mickmackusa.

Upvotes: 2

mickmackusa
mickmackusa

Reputation: 48001

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

  1. Iterate the input array to access the keys and values.
  2. 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.
  3. 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
  4. 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);

Upvotes: 1

splash58
splash58

Reputation: 26153

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

demo

Upvotes: 3

Related Questions