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.