PHP Arrays - Separate Identical Values

Question

Is there any good or standard way of doing this?

Take the following example:

$values = array(
    'blue'
    , 'blue'    
    , 'blue'
    , 'blue'
    , 'green'
    , 'red'
    , 'yellow'
    , 'yellow'
     , 'purple'
    , 'purple'
    , 'purple'
);

I need it to be separated so no two identical values are touching (unless there is no possible solution -- in which case either generating an error, returning false or anything else is acceptable).

Here's the above array (done by hand) but how I am trying to change it:

$values = array(
    'blue'
    , 'purple'
    , 'green'
    , 'purple'
    , 'blue'
    , 'red'
    , 'blue'
    , 'yellow'
    , 'blue'
    , 'yellow'
    , 'purple'
)

The values won't necessarily be in order in the beginning -- that was just for simplicities sake.

Any ideas? Any code to get me started in the right direction?

Paul · Accepted Answer · 2012-06-13 06:33:29Z

4

This function should do the trick:

function uniq_sort($arr){
    if(!count($arr))
        return array();

    $counts = array_count_values($arr);
    arsort($counts);
    while(NULL !== ($key = key($counts)) && $counts[$key]){
        if(isset($prev) && $prev == $key){
            next($counts);
            $key = key($counts);
            if($key === NULL)
                return false;
        }
        $prev = $result[] = $key;

        $counts[$key]--;
        if(!$counts[$key])
            unset($counts[$key]);

        arsort($counts);
        reset($counts);
    }
    return $result;
}

Example usage:

$values = array('blue', 'blue', 'blue', 'blue', 'green', 'red', 'yellow', 'yellow', 'purple', 'purple', 'purple');
print_r(uniq_sort($values));

$values = array('a', 'b', 'b');
print_r(uniq_sort($values));

$values = array(1);
print_r(uniq_sort($values));

$values = array(1, 1, 1, 1, 2, 3, 4);
print_r(uniq_sort($values));

$values = array(1, 1, 1, 1, 2, 3);
var_dump(uniq_sort($values));

And output:

Array
(
    [0] => blue
    [1] => purple
    [2] => blue
    [3] => yellow
    [4] => blue
    [5] => purple
    [6] => blue
    [7] => purple
    [8] => red
    [9] => yellow
    [10] => green
)
Array
(
    [0] => b
    [1] => a
    [2] => b
)
Array
(
    [0] => 1
)
Array
(
    [0] => 1
    [1] => 3
    [2] => 1
    [3] => 4
    [4] => 1
    [5] => 2
    [6] => 1
)
bool(false)

edited Jun 13, 2012 at 6:33

answered Jun 13, 2012 at 3:43

Paul

142k28 gold badges285 silver badges272 bronze badges

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

3 Comments

Paul Over a year ago

@Kerry No problem, and I take back what I said in my original revision about it being able to be optimized by removing the arsort from the loop. It turns out it's ridiculously hard to swap the position of two key/value pairs in a PHP array, and the solution would probably be slower than a call to arsort

Kerry Jones Over a year ago

Great -- looks good to me, it's one of those functions that I had never thought needing before today

goat Over a year ago

Nice. I feel that the method used(always choosing the highest frequency first) is guaranteed to find a solution, if a solution exists.

wecsam · Accepted Answer · 2012-06-13 03:15:34Z

1

$values = array(
        'blue'
        , 'blue'    
        , 'blue'
        , 'blue'
        , 'green'
        , 'red'
        , 'yellow'
        , 'yellow'
        , 'purple'
        , 'purple'
        , 'purple'
    );
    $value_count = Array();
    foreach($values as $v){
        if(isset($value_count[$v])){
            $value_count[$v]++;
        }else{
            $value_count[$v] = 1;
        }
    }
    unset($v);
    //Now generate new array 
    $result = Array();//This line is technically not necessary 
    $done = false;
    while(!$done){
        $done = true;
        foreach($value_count as $k => &$c){
            if($c > 0){
                $result[] = $k;
                $c--;
                $done = false;
            }
        }
    }
    print_r($result);

This results in this:

Array
(
    [0] => blue
    [1] => green
    [2] => red
    [3] => yellow
    [4] => purple
    [5] => blue
    [6] => yellow
    [7] => purple
    [8] => blue
    [9] => purple
    [10] => blue
)

answered Jun 13, 2012 at 3:15

wecsam

2,7814 gold badges28 silver badges46 bronze badges

5 Comments

Paul Over a year ago

This doesn't really work. It works for the example input array, but it doesn't work for a lot of other arrays. Say [1, 1, 1, 1, 2, 3, 4]. A solution would be [1, 2, 1, 3, 1, 4, 1], but your code returns [1, 2, 3, 4, 1, 1, 1] which is incorrect.

Matt Dodge Over a year ago

ascii-lime is correct. However, I think if you sort by descending value counts after you compute the counts it should work properly. Basically, start filling the result array with the elements that have the highest count

Paul Over a year ago

@mattedgod Yes that should work. You should also keep track of the previous value added and then if the value with the highest count is the same as the previous value use the one with the second highest count instead. If you hit the situation where there is only one unique element left and it's also your previous element then you return false.

Matt Dodge Over a year ago

Also, a side note: I think there will always be a valid solution as long as one element never has more than (n+1)/2 occurrences

Kerry Jones Over a year ago

@Ascii-lime -- could you show the updated code? I'm actually trying to make it work in an multi dimensional array an array of associative arrays

Kleber S. · Accepted Answer · 2012-06-13 03:25:15Z

1

the logical:

print the first value, before print the next, compare it to the previous one, if they are same, jump over the next and so on.

answered Jun 13, 2012 at 3:25

Kleber S.

8,3006 gold badges45 silver badges70 bronze badges

9 Comments

Kerry Jones Over a year ago

And if three of them are identical in the end like the above example?

Kleber S. Over a year ago

it will jump to the next value.

Matt Dodge Over a year ago

What happens with ['a','b','b']? I don't think this works with that

Matt Dodge Over a year ago

@KleberS But ['b','a','b'] is a valid solution to that list and your algorithm returns false. The key to this (most likely homework) problem is that you need to sort the elements by the most frequent first.

Matt Dodge Over a year ago

@Kerry Haha I was kidding about the hw, if it was someone with no rep asking the question I would have been much more skeptical. Just reminds me of those "fun" algorithm problems from college. That being said, I think the wecsam's answer with the sorting addition is your best bet

|

sczizzo · Accepted Answer · 2012-06-13 03:12:40Z

0

Walk down the array, remember the last value you saw, and throw away the one you're looking at if it matches. Here's an example:

$values = array(
    'blue'
    , 'blue'    
    , 'blue'
    , 'blue'
    , 'green'
    , 'red'
    , 'yellow'
    , 'yellow'
     , 'purple'
    , 'purple'
    , 'purple'
);

$last_seen_value = NULL;
foreach ($values as $i => $value) {
  if (0 == strcmp($value, $last_seen_value)) {
    unset($values[$i]);
  } else {
    $last_seen_value = $value;
  }
}

print_r($values);

# Output:
# 
# Array
# (
#     [0] => blue
#     [4] => green
#     [5] => red
#     [6] => yellow
#     [8] => purple
# )

edited Jun 13, 2012 at 3:12

answered Jun 13, 2012 at 3:06

sczizzo

3,20622 silver badges28 bronze badges

1 Comment

Matt Dodge Over a year ago

This will just output the unique values. I think what the OP wants is the array "shuffled" so that no two same values are touching. In other words, the output array should be the same size as the input array.

Collectives™ on Stack Overflow

PHP Arrays - Separate Identical Values

4 Answers 4

3 Comments

5 Comments

9 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

5 Comments

9 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related