Getting All Permutations Of An Array In PHP

Here are two ways in which you can figure out all of the different permutations of an array.

The first is using a recursive algorithm. This nibbles apart the array and sticks it back together again, eventually resulting in all of the different permutations available.

$list = array();
function recursive_permutations($items,$perms = array( ))
{
 static $list;
 if (empty($items)) {
  $list[] = join(',', $perms);       
 } else {
  for ($i = count($items)-1;$i>=0;--$i) {
   $newitems = $items;
   $newperms = $perms;
   list($foo) = array_splice($newitems, $i, 1);
   array_unshift($newperms, $foo);
   recursive_permutations($newitems, $newperms);
  };
  return $list;
 };
}
$perms = recursive_permutations(range(1,3));
echo '<pre>' . print_r($perms, true) . '</pre>';

The alternative is to use a force method that simply shuffles the array and then converts the resulting array pattern in a as a string. These strings are then used as keys for another array. After enough iterations the outer array should contain all of the permutations possible. This is by no means elegant or nice, but it works very well with smaller arrays.

function permutations($array)
{
 $list = array();
 for ($i=0; $i<=10000; $i++) {
  shuffle($array);
  $tmp = implode(',',$array);
  if (isset($list[$tmp])) {
   $list[$tmp]++;
  } else {
   $list[$tmp] = 1;
  }
 }
 ksort($list);
 $list = array_keys($list);
 return $list;
}
$perms = permutations(range(1, 3));
echo '<pre>' . print_r($perms, true) . '</pre>';

Update 18/05/2011:
Looking back at this code I can see that it is a little intensive as it will always run the array 10,000 times, even if all of the permutations have been found. To prevent it always running the full 10,000 iterations of the loop it is possible to find how many permutations would be found by working out the factorial of the length of the array. We can then stop the array once this limit has been reached.

function permutations($array) {
    $list = array();
    
    $array_count = count($array);
    
    $number_of_permutations = 1;
    if ($array_count > 1) {
        for ($i = 1; $i <= $array_count; $i++) {
            $number_of_permutations *= $i;
            echo $number_of_permutations . ' ' . $i . "\n";
        }
    }

    for ($i=0; count($list) < $number_of_permutations; $i++) {
        shuffle($array);
        $tmp = implode(',', $array);
        if (!isset($list[$tmp])) {
            $list[$tmp] = 1;
        }
    }

    ksort($list);
    $list = array_keys($list);
    return $list;
}