Shuffling an array, but with a twist.

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
User avatar
onion2k
Jedi Mod
Posts: 5263
Joined: Tue Dec 21, 2004 5:03 pm
Location: usrlab.com

Shuffling an array, but with a twist.

Post 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.
M2tM
Forum Commoner
Posts: 41
Joined: Sat Feb 27, 2010 12:35 pm

Re: Shuffling an array, but with a twist.

Post 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.
Post Reply