Jonline Jonline - 3 months ago 7x
PHP Question

Creating an array sorting function that ensures like values aren't adjacent

I have an array of objects with a

property; there are 5 possible 'types'. Importantly, the elements are inserted into the array and the randomness should be preserved as much as possible; it's only 3rd-party software constraint that's forcing this non-adjacency business.

I want to sort that array so that no adjacent values are alike, or, if this proves impossible, to ensure that the unsortable pairs arrive at the bottom.

I've tried this:

function check_adjacency($obj_1, $obj_2) {
return $obj_1->type == $obj_2->type ? 0 : 1; // also tried -1
usort($arr, "check_adjacency");

I can sort of see why this doesn't work; there's no criterion for returning 1 vs -1. But I'm stumped on how to (effectively) write this in PHP. I also tried writing my own function to achieve this but I keep ending up completing too early or with infinite loops. Strategic advice as much as solutions both welcome.


Following requests for an example:

I've used sequential variable names for convenience, but in fact the objects are added to the array in a random order with regard to their

$objs = [ $obj_1, $obj_2, $obj_3, $obj_$4... $obj_300];
foreach($objs as $o) print $o->type


>> "t2", "t1", "t1", "t2", "t2", "t4", "t3", "t3", "t3", "t5", "t1", "t2"...

Ideally, after sorting, something like this would obtain.

>> "t2", "t1", "t2", "t4", "t3", "t1", "t3", "t2", "t3", "t5", "t1", "t2"

Basically, if the next element in the set has the same
property as the one preceding it, remove it and insert at the earliest index thereafter. Let me know if this hasn't clarified things.

Edit The 2nd:

Thought of a simpler way to explain this. I have a whole lot of books—small books, medium books, and large books. All have different titles; I want a bookshelf on which no two books of the same size sit beside one and other, and which are otherwise randomly distributed.


Do this in two steps. First create a 2-dimensional array whose keys are the type properties, and elements are an array of all the items with that type. Then loop through these keys, removing one item from each group and adding it to the result array.

// step 1
$arr_by_type = array();
foreach ($arr as $el) {
    if (isset($arr_by_type[$el->type])) {
        $arr_by_type[$el->type][] = $el;
    } else {
        $arr_by_type[$el->type] = array($el);

// step 2
$result = array();
while (!empty($arr_by_type)) {
    foreach ($arr_by_type as $type => &$sub_array) {
        $result[] = array_pop($sub_array);
        if (empty($sub_array)) {