Search code examples
phparraysalgorithmsortingarray-column

Sort a 2D array by column value into recurring ascending groups of not more than N of a kind

I have an array that contains other associative arrays as its values. Each one of these "sub" arrays is mapped with key-value pairs:

$items = [
    ['type' => 1, 'text' => 'A'],
    ['type' => 2, 'text' => 'B'],
    ['type' => 2, 'text' => 'C'],
    ['type' => 3, 'text' => 'D'],
    ['type' => 2, 'text' => 'E'],
    ['type' => 1, 'text' => 'F'],
    ['type' => 4, 'text' => 'G'],
    ['type' => 2, 'text' => 'H'],
    ['type' => 1, 'text' => 'I'],
    ['type' => 4, 'text' => 'J'],
    ['type' => 2, 'text' => 'K'],
    ['type' => 4, 'text' => 'L'],
    ['type' => 2, 'text' => 'M'],
    ['type' => 3, 'text' => 'N'],
    ['type' => 3, 'text' => 'O'],
    ['type' => 1, 'text' => 'P'],
    ['type' => 1, 'text' => 'Q'],
    ['type' => 2, 'text' => 'R'],
    ['type' => 3, 'text' => 'S'],
    ['type' => 2, 'text' => 'T'],
    ['type' => 3, 'text' => 'U'],
    ['type' => 2, 'text' => 'V'],
    ['type' => 3, 'text' => 'W'],
    ['type' => 2, 'text' => 'X'],
    ['type' => 4, 'text' => 'Y'],
    ['type' => 2, 'text' => 'Z'],
];

How can I sort this array and return as another array, with the following requirements?

  1. It needs to sort the associative arrays by its type.
  2. It needs to do this by picking the first 3 items that show up in the $items array, and then moving on to the next type, which is 2, and doing the same. The max amount of types there are in my code is 8, but theoretically it should work with any number.
  3. If it has picked out 3 of each type one time, restart again with the remainder of items in the array, starting at type 1 again.

Essentially you should get another array which -- from top to bottom -- has values with their types in alternated orders, something like this:

[
    ['type' => 1, 'text' => 'A'],
    ['type' => 1, 'text' => 'F'],
    ['type' => 1, 'text' => 'I'],
    ['type' => 2, 'text' => 'B'],
    ['type' => 2, 'text' => 'C'],
    ['type' => 2, 'text' => 'E'],
    ['type' => 3, 'text' => 'D'],
    ['type' => 3, 'text' => 'N'],
    ['type' => 3, 'text' => 'O'],
    ['type' => 4, 'text' => 'G'],
    ['type' => 4, 'text' => 'J'],
    ['type' => 4, 'text' => 'L'],
    ['type' => 1, 'text' => 'P'],
    ['type' => 1, 'text' => 'Q'],
    ['type' => 2, 'text' => 'H'],
    ['type' => 2, 'text' => 'K'],
    ['type' => 2, 'text' => 'M'],
    ['type' => 3, 'text' => 'S'],
    ['type' => 3, 'text' => 'U'],
    ['type' => 3, 'text' => 'W'],
    ['type' => 4, 'text' => 'Y'],
    ['type' => 2, 'text' => 'R'],
    ['type' => 2, 'text' => 'T'],
    ['type' => 2, 'text' => 'V'],
    ['type' => 2, 'text' => 'X'],
    ['type' => 2, 'text' => 'Z'],
]

The text does not matter to the sorting.

I've actually gone as far as to make a YouTube video to better explain what should happen: Video

My current thought process was to use a separate array called $groups, use a foreach loop eight different times, and in each one, continue the loop if it's not for the specific type. For example:

// My above $items array example here

// Initialize $groups
$groups = [];

// foreach for type 1
foreach ($items as $item) {
    // If any of the items are not of type 1, ignore and continue
    if ($item["type"] !== 1) {
        continue;
    }
    // Otherwise, push to $groups
    array_push($groups, $item["type"];
}

// foreach for type 2
foreach ($items as $item) {
    // If any of the items are not of type 2, ignore and continue
    if ($item["type"] !== 2) {
        continue;
    }
    // Otherwise, push to $groups
    array_push($groups, $item["type"];
}

// Do this for each possible type, up to type 8

This not only does this seem extremely inefficient and backwards, I just feel there is a better way to go about it or another angle I'm missing. I don't believe the above code is even close to the solution.

Solution

  • I think setting up array_multisort() to do this job makes logical sense (since this is a sorting task).
    Note that my demonstration will sort the actual input array (make yourself a copy if you need to preserve the original).

    1. Iterate the input array.
    2. Populate a flat mapping array with increasing grouping ids.
    3. Populate a flat mapping array of type values.
    4. Call array_multisort() to sort on $grouper, then $column, then $items (then you can access $items).

    Code: (Demo) (Alt Demo)

    $maxConsecutive = 3;

$grouper = [];
$column = [];
foreach ($items as $row) {
    $column[] = $row['type'];  // preserve isolated type values
    $encountered[$row['type']] ??= 0; // declare the default value of 0 for the first encounter of a given type value
    $grouper[] = intdiv($encountered[$row['type']]++, $maxConsecutive); // access the cached counter for the given type, divide it by 3, omit any decimal values; then increment the counter (post-incrementation `++` only increases the value AFTER it is used)
}

array_multisort($grouper, $column, $items); // sort by grouper ASC, column ASC, then items ASC
var_export($items);

    Somewhat related is Sort a flat array in recurring ascending sequences which has a hardcoded grouping N of 1 (instead of 3) while sorting data in ascending recurring sequences.

    Alternatively, you can group the data into subsets, then sort, then consume the grouped data while populating the new result.
    Though, I will state that this doesn't feel as professional as the array_multisort() approach for a sorting task.

    1. Group the rows by their type value.
    2. Sort by the new first level keys.
    3. Use a self-extending foreach() loop (notice the & in the signature) to push only the first N rows per group into the result array. If the current group still has elements, push the whole group onto the end of the array.

    Code: (Demo)

    $maxConsecutive = 3;

$grouped = [];
foreach ($items as $row) {
    $grouped[$row['type']][] = $row;
}

ksort($grouped);

$result = [];
foreach ($grouped as &$group) {
    array_push($result, ...array_splice($group, 0, $maxConsecutive));
    if ($group) {
        $grouped[] = $group;
    }
}
var_export($result);

    As a microoptimization, you can extract the entire payload of the last remaining group with: (Demo)

    array_push($result, ...array_splice($group, 0, count($grouped) === 1 ? null : $maxConsecutive));