Page 1 of 1

Shuffling an array, but with a twist.

Posted: Thu Mar 18, 2010 2:08 pm
by onion2k
I have an array of items. Eg

Code: Select all

 
  $array = array("Bob", "Jim", "Jim", "Sally", "Sally", "Sally", "Frank", "William", "William");
 
I need to keep the duplicates and shuffle the array (randomly) in a way that means no two similar items are next to each other.

I could brute force it (shuffle, check it worked, shuffle again if it didn't. Repeat until it worked.) but I imagine it's something that has an elegant solution. I can't see it though.

Re: Shuffling an array, but with a twist.

Posted: Thu Mar 18, 2010 3:42 pm
by M2tM
Alright, here it is, comments welcome:

Code: Select all

 
<?php
 
function randomShuffleNoConsecutive($array){
    $resultArray = array();
    if(($symbols = randomShuffleNoConsecutiveIsSolveable($array)) !== false){
        $total = count($symbols);
        $lastSelectedIndex = null;
        while($total > 0){
            while(($selectedIndex = randomArrayIndex($symbols)) === $lastSelectedIndex){;}
            $resultArray[] = $selectedIndex;
            $symbols[$selectedIndex]--;
            if($symbols[$selectedIndex] == 0){
                unset($symbols[$selectedIndex]);
                $total--;
            }
            $lastSelectedIndex = $selectedIndex;
        }
        return $resultArray;
    }
    return false;
}
 
function randomArrayIndex($array){
    if(is_array($array)){
        $IndexList = array_keys($array);
        return $IndexList[mt_rand(0, count($IndexList)-1)];
    }
    return false;
}
 
function randomShuffleNoConsecutiveIsSolveable($array){
    $maxCount = ceil(count($array) / 2) + 1;
    foreach($array as $value){
        if(!isset($counts[$value])){$counts[$value] = 0;} //required to avoid a notice
        $counts[$value]++;
        if($counts[$value] >= $maxCount){
            return false;
        }
    }
    return $counts;
}
 
$array = array("Bob", "Jim", "Jim", "Sally", "Sally", "Sally", "Frank", "William", "William");
print_r(randomShuffleNoConsecutive($array));
?>
 
I approached this problem from a few angles originally, but this seems to work best.