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

Question

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.

Answer 1

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

Answer 2

First of all

I can't seem to find an algorithm to match what I'm trying to do. I can't seem to find much, and I'm beginning to wonder if the algorithm I'm looking for doesn't actually exist yet

yes, you are right, it does not exists and should not exists ever, the Algorithm should not be exists to output a specific result. it should be used to perform a specific behavior/function rather than achieve/output a specific result.

however, you can sort an array based on it's key using uasort like following:

$items = [
    ["type" => 1, "text" => "Type of 1"],
    ["type" => 1, "text" => "Type of 1"],
    ["type" => 1, "text" => "Type of 1"],
    ["type" => 1, "text" => "Type of 1"],
    ["type" => 2, "text" => "Type of 2"],
    ["type" => 2, "text" => "Type of 2"],
    ["type" => 2, "text" => "Type of 2"],
    ["type" => 2, "text" => "Type of 2"],
];

uasort($items, fn ($a, $b) => $a > $b ? 1 : -1); 

print_r($items);

Then, you can use something like array_column in a combination with implode to extract the item as a value in a one-linear fashion, or you can use the foreach loops as you already mentioned.

Answer 3

This first creates a count of each type, then loops till there is nothing output. The inner loop will output the number of items you want (as long as that type has something left to output) adjusting the remaining left as you go along.

I've commented the code which should explain it clearer.

// Create text lookup array, indexed by type
$types = array_column($items, null, 'type');
// Count the number of each type there are
$breakdown = array_count_values(array_column($items, 'type'));

// Sort by the key to create desired order
ksort($breakdown);

$breakSize = 3;

do {
    // If flag doesn't change then nothing is left to output
    $anyOutput = false;
    foreach ($breakdown as $key => &$countLeft) {
        // Loop while less than the break size but also with something left
        for ($i = 0; $i < $breakSize && $countLeft > 0; $i++) {
            echo $types[$key]['text'] . PHP_EOL;
            // Adjust amount left
            $countLeft--;
            // Flag something put out
            $anyOutput = true;
        }
    }
} while ($anyOutput);

Update: If you have different text values for some of the types, it would need to keep track of this data.

So this code creates an array of each type and a list of the text values for each one, then in the loop it removes the first from the list at each point (using array_shift) to output the next one and remove it from the remaining list.

// Split into groups by the type
$breakdown = [];
foreach ($items as $item) {
    $breakdown[$item['type']][] = $item['text'];
}
// Sort by the key to create desired order
ksort($breakdown);

$breakSize = 3;

do {
    // If flag doesn't changem then run out of content
    $anyOutput = false;
    foreach ($breakdown as $key => &$textList) {
        // Loop while less than the break size but also with something left
        for ($i = 0; $i < $breakSize && !empty($textList); $i++) {
            echo array_shift($textList) . PHP_EOL;
            // Flag something put out
            $anyOutput = true;
        }
    }
} while ($anyOutput);