Sorting an array based on a condition

Question

I have the following array

$records = array(

    array("postId"=>"1","grid"=>"6"),
    array("postId"=>"2","grid"=>"3"),
    array("postId"=>"3","grid"=>"6"),
    array("postId"=>"4","grid"=>"3"),
    array("postId"=>"5","grid"=>"3"),
    array("postId"=>"6","grid"=>"12"),
    array("postId"=>"7","grid"=>"3"),

);

I want to sort this array in a way that the sum of any number of back to back "grids" is equals to 12.

Example: The values of the "grids" in the above array are : 6,3,6,3,3,12,3

(6+6=12), (3+3+3+3=12),(12=12) so the new order should be 6,6,3,3,3,3,12 or 3,3,3,3,12,6,6 or 6,3,3,6,3,3,12

So after sorting the array the new array should look like following:

$records=array(

    array("postId"=>"1","grid"=>"6"),
    array("postId"=>"3","grid"=>"6"),
    array("postId"=>"2","grid"=>"3"),       
    array("postId"=>"4","grid"=>"3"),
    array("postId"=>"5","grid"=>"3"),
    array("postId"=>"7","grid"=>"3"),
    array("postId"=>"6","grid"=>"12"),

);

I searched in php manual and found these functions: sort,uasort, uksort, usort but I couldn't figure out how to use them.

Could you please tell me how to achieve this using PHP ?

Update

The value of grid will always be 3 or 6 or 12 (these three numbers only )

Problem

  $records = array(

    array("postId"=>"1","grid"=>"3"),
    array("postId"=>"2","grid"=>"6"),    
    array("postId"=>"3","grid"=>"3"),     
    array("postId"=>"4","grid"=>"3"),
    array("postId"=>"5","grid"=>"6"),
    array("postId"=>"6","grid"=>"6"),    
    array("postId"=>"7","grid"=>"3"),
    array("postId"=>"8","grid"=>"6"),

 );

There's no silver bullet for this, it's going to require you write a pretty extensive function from scratch. — TravisO
– TravisO, Commented Sep 24, 2013 at 19:55
Would IDs 1, 2, 4, 3, 5, 7, 6 also be acceptable? What is the preferred one? — Wolfgang Stengel
– Wolfgang Stengel, Commented Sep 24, 2013 at 19:57
any number of back to back "grids" => what's that supposed to mean? — Jon
– Jon, Commented Sep 24, 2013 at 19:59
You probably can't do this using php's sort functions since those functions assume there's a way of comparing two objects and determining which one is bigger or smaller. In your example, you don't have a notion of one object being greater than or smaller than another. Rather, you are trying to group based on their grid values adding up to 12. — Gevork Palyan
– Gevork Palyan, Commented Sep 24, 2013 at 19:59
@WolfgangStengel IDs are not an issue here :) thanks for your reply — black_belt
– black_belt, Commented Sep 24, 2013 at 20:00

dev-null-dweller · Accepted Answer · 2013-09-25 22:41:08Z

4

So you are not really sorting, but reordering to create sequence. I imagine that you are trying to do some layout of bricks with fixed height, and you need to have it reordered to fill each row and leave the rest at the end. With given fixed variants of 12,6,3 it can be done by sorting it in descending order - with odd number of sixes it will be filled with smaller threes. However such order will produce boring layout - to have it more interesting you only need to reorder some posts. For this you will need to create temporary container and merge it when sum of its grids is equal 12. If you are left with some temporary containers, merge them into one and sort descending before merging with previously grouped.

Code illustrating my concept:

//auxiliary function to calculate sum of grids in given temporary container
    function reduc($a) {
    return array_reduce($a, function ($result, $item) {
        return $result . $item['grid'] . ',';
    }, '');
}

function regroup($records, $group_sum = 12) {
    $temp = array();
    $grouped = array();

    foreach ($records as $r) {
        if ($r['grid'] == $group_sum) {
            $grouped[] = $r;
        } else {
            if (!$temp) {
                $temp[] = array($r);
            } else {
                $was_grouped = false;
                foreach ($temp as $idx => $container) {
                    $current_sum = sum_collection($container);
                    if ($current_sum + $r['grid'] <= $group_sum) {
                        $temp[$idx][] = $r;
                        if ($current_sum + $r['grid'] == $group_sum) {
                            $grouped = array_merge($grouped, $temp[$idx]);
                            unset($temp[$idx]);
                        }
                        $was_grouped = true;
                        break;
                    }
                }
                if (!$was_grouped) {
                    $temp[] = array($r);
                }
            }
        }
    }

    if ($temp) {
        //Sort descending, so biggest ones will be filled first with smalller
        $rest = call_user_func_array('array_merge', $temp);
        usort($rest, function($a, $b) {
            return $b['grid'] - $a['grid'];
        });
        $grouped = array_merge($grouped, $rest);
    }

    return $grouped;
}

edited Sep 25, 2013 at 22:41

answered Sep 24, 2013 at 23:10

dev-null-dweller

29.5k3 gold badges68 silver badges87 bronze badges

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

3 Comments

black_belt Over a year ago

How did you understand that I am trying to create a layout? This is exactly what I am trying to do :) . Descending the order was really producing a boring layout. Your code is very intelligent and produces what I exactly wanted. May be I couldn't explain everything clearly in my question but somehow you understood it and developed a super code for me. Your code is not just sorting by ascending /descending the order but doing a real calculation to find out a sequence that you can use to create a nice template layout. I cannot thank you enough man. You have helped me a lot. You are a genius. :)

black_belt Over a year ago

Please check the "Problem" part of my question. If I use the array that I shown in the problem part, I get duplicate values. Thanks

dev-null-dweller Over a year ago

Well, this was quick and dirty proof of concept, bugs were expected. I fixed it, but it is not production-grade code so I encourage to implement it on your own :)

The Alpha · Accepted Answer · 2013-09-24 21:02:21Z

2

The question is:

I want to sort this array in a way that the sum of any number of back to back "grids" is equals to 12.

You may try this (using usort)

$records = array(
    array("postId"=>"1","grid"=>"6"),
    array("postId"=>"2","grid"=>"3"),
    array("postId"=>"3","grid"=>"6"),
    array("postId"=>"4","grid"=>"3"),
    array("postId"=>"5","grid"=>"3"),
    array("postId"=>"6","grid"=>"12"),
    array("postId"=>"7","grid"=>"3"),
);

You have number 34 times, nimber 6 2 times and number 12 once.

// Sort (ASC)
usort($records, function($a, $b) {
    return $a['grid'] - $b['grid'];
});

DEMO-1 (ASC) (3+3+3+3=12, 6+6=12, 12=12).

// Sort (DESC)
usort($records, function($a, $b) {
    return $b['grid'] - $a['grid'];
});

DEMO-2 (DESC) (12=12, 6+6=12, 3+3+3+3=12).

Output after sort using (ASC) :

Array (

[0] => Array
    (
        [postId] => 7
        [grid] => 3
    )

[1] => Array
    (
        [postId] => 5
        [grid] => 3
    )

[2] => Array
    (
        [postId] => 4
        [grid] => 3
    )

[3] => Array
    (
        [postId] => 2
        [grid] => 3
    )

[4] => Array
    (
        [postId] => 3
        [grid] => 6
    )

[5] => Array
    (
        [postId] => 1
        [grid] => 6
    )

[6] => Array
    (
        [postId] => 6
        [grid] => 12
    )

)

edited Sep 24, 2013 at 21:02

answered Sep 24, 2013 at 20:06

The Alpha

147k30 gold badges294 silver badges313 bronze badges

19 Comments

kero Over a year ago

Yes, grids should result in 12. Your comparison doesn't do that but just sorts from lowest to highest number

Wolfgang Stengel Over a year ago

Yes, I suppose you're right, but I'm sure the answer does not help. If the OP only was interested in this particular array, he would sort it by hand once and be done with it. Having 25k reputation you have to be kidding :)

Wolfgang Stengel Over a year ago

I apologize, indeed you simply need to sort descending to get the desired result for all examples I can think of. Somehow I thought a 9 should be possible as well (as it's a multiple of 3) but the OP clearly excluded this. Kudos.

black_belt Over a year ago

@SheikhHeera Thank you very much for your help and thanks to Wolfgang Stengel as well :)

black_belt Over a year ago

Yes both your answer and Wolfgang Stengel's answer worked for me, I have accepted your answer because you answered the question first :) Thanks a lot :) I wish I could be a PHP expert like you guys

|

Wolfgang Stengel · Accepted Answer · 2013-09-24 20:50:12Z

1

This solution first sorts by grid size descending and then brute forces it's way down by testing each remaining element against the sum so far for each row:

$sum=0;
$grouped=array();
usort($records, function($a, $b) { return $a['grid']<$b['grid']; });
while ($records)
{
    $next=reset($records);
    if ($sum) foreach ($records as $next) if ($sum+$next['grid']<=12) break;
    $grouped[]=$next;
    $sum+=$next['grid'];
    unset($records[array_search($next, $records)]);
    if ($sum>=12) $sum=0;
}

Update

Turns out that sorting in descending order is enough to solve the requirement using only 3, 6 and 12 elements. A 12 as well as a 6 followed by a 6 stand alone, and all other combinations are filled up with remaining threes. (For some reason I thought the algorithm would have to be able to deal with nines as well.) So this is all you need:

usort($records, function($a, $b) { return $a['grid']<$b['grid']; });

Granted this makes for a very boring grid.

edited Sep 24, 2013 at 20:50

answered Sep 24, 2013 at 20:22

Wolfgang Stengel

2,8561 gold badge19 silver badges22 bronze badges

3 Comments

black_belt Over a year ago

Thank you very much for your answer. Could you please tell me how to use your solution because print_r($records); is not giving me any result :)

Wolfgang Stengel Over a year ago

The records are put into $grouped.

black_belt Over a year ago

Please imagine a sequence like this 6,3,3,3,6,6 if you sort this the way I wanted it should be like this 6,6,3,3,6,3 (6+6 =12 3+3+6= 12, 3 is remaing) but your code is just sorting it like this 3,3,3,6,6,6

dev-null-dweller · Accepted Answer · 2013-09-24 20:34:07Z

0

In PHP >= 5.3.0 you can do this with usort() and closures (or globals as a hack). Given $records:

$running_length = 0;
usort( $records, function( $a, $b ) use( $running_length ) {
    $running_length += $a["grid"];
    if( $running_length >= 12 ) return( true );
    return( false );
});

If you visualize "grid" parameter as a string length, the end result, $records, becomes ordered like:

...            3
...            3
......         6
...                3
......             6
...                3
............  12

Given randomness of available chunks, you may want to sort this array first from smallest-to largest and then see whether it gets arranged better for you. This method obviously doesn't detect fragmentations and blocks that don't fit --- or can't resolve to fit.

edited Sep 24, 2013 at 20:34

dev-null-dweller

29.5k3 gold badges68 silver badges87 bronze badges

answered Sep 24, 2013 at 20:19

pp19dd

3,6232 gold badges18 silver badges21 bronze badges

1 Comment

Wolfgang Stengel Over a year ago

How on earth does this work? ;-) You're not supposed to know the order in which the array elements are passed into the comparison function?

Collectives™ on Stack Overflow

Sorting an array based on a condition

Update

Problem

4 Answers 4

3 Comments

19 Comments

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Update

Problem

4 Answers 4

3 Comments

19 Comments

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related