Sorting a PHP array of objects such that adjacent objects don't share specific property values

Question

I have to sort an array objects (all of the same class); each object as a type property which always stores 1 of 5 possible integer values (call them 1-5 for the sake of convenience). In this strange use-case, the objects must be randomly ordered within the array with the single condition that no two objects, in sequence, can share the same type value.

ie. If the array were:

$objects = [$t_1, $t_1, $t_2, $t_2]

where $t_1 indicates an object whose type property is 1

Then the following order is fine:

$objects = [$t_1, $t_2, $t_1, $t_2]

But the initial state is not.

I'm currently doing something like this (the verbatim code is too confusingly in situ to post, but this is identical, logically, to what I've currently written):

$unsorted = $array_of_objects
$sorted = [];
while ( count( $unsorted ) ) {
    // randomly select a remaining unsorted object
    $next_index = array_rand( $unsorted );
    $next_obj   = $unsorted[ $next_index ];

    // as long as the current object's type property doesn't match the type property of the preceding obj, add it to $sorted
    if ( !count( $sorted ) or ( $next_obj->type != $sorted[ -1 ]->type ) ) {
        array_push( $sorted, $next_obj );
        unset( $unsorted[ $next_index ] );
    }           
}

But I have the intuition that this inefficient, and of course it has problem of running forever if there is no sorting solution.

Looking for advice on how to do this better and/or more robustly.

And what should the behavior be if 3 of 4 objects have the same type? — Patrick Q
– Patrick Q, Commented Jul 31, 2018 at 19:30
Also, if you have code that's working, and you just want to improve the performance, you might be better off at codereview.SE — Patrick Q
– Patrick Q, Commented Jul 31, 2018 at 19:35
Does the function have to return all possbile random orderings or is it allowed to make some pre-conditions to the result "random" ordering? — Philipp
– Philipp, Commented Jul 31, 2018 at 20:37
@Phillip Well, the context is experimental psychology, so as-random-as-possible is ideal because obviously biases here could result in biases in experimental data. But, as only one solution is need, returning any ordering solution is fine. What sort of pre-conditions were you imagining? — Jonline
– Jonline, Commented Aug 1, 2018 at 11:23
@PatrickQ It should throw an error, in this case; the user is considered to have given bad data if no solution is possible. — Jonline
– Jonline, Commented Aug 1, 2018 at 11:25

Dmytro Zasiadko · Accepted Answer · 2018-08-03 23:10:20Z

1

@update Figured out that previous answer was not correct.

Take a look at this code - https://www.tehplayground.com/CcHyHA54oYhyKmDi You may need to run it few times, because it throws an exception when it is not possible to sort array in the way we need it to be sorted.

edited Aug 3, 2018 at 23:10

answered Jul 31, 2018 at 19:38

Dmytro Zasiadko

1415 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Jonline Over a year ago

So I tried to work this solution into my context; certainly, it works well in your sample. After extensive testing, I cannot get this to stop throwing the BadData exception; for my purposes, there are usually hundreds of elements to sort. I admit that your code is a touch over my head, so it's hard for me to figure out why this is never finding a solution (when, checking by hand at least once, I know that there ought to have been one).

Dmytro Zasiadko Over a year ago

Algorithm is quite simple. To define what element should next be added to result array, it takes the random one with the biggest count. So for example, if we have an array [$a, $b, $c, $a, $b, $c, $a, $b, $c, $a] the first item in result will be $a and the next one will be random from $b or $c. So items which are represented most will always be st the beginning of result array. Probably can you provide a data set you mentioned in your comment?

Jonline Over a year ago

I can provide a data set, but truly there's no difference to what you've generated except quantity. The context is cognitive science; the sample I was trying to shunt through your algorithm contained 576 objects, wherein only 3 types (which represent angles, so, 45, -45, and 0) were each represented 192 times. Perhaps the even distribution of samples was problematic for an algo that assumes a largest set? Even distributions aren't the rule, in any case, this is jsut the data set I was given to work with as a starting point.

Dmytro Zasiadko Over a year ago

I changed the code in playground to use your data set - algorithm founds solution, it doesn't throw exception.

Collectives™ on Stack Overflow

Sorting a PHP array of objects such that adjacent objects don't share specific property values

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related