Getting All Permutations Of An Array In PHP

29th February 2008 - 3 minutes read time

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;
}

 

Comments

Permalink
You just keep calling shuffle() until you find a combination that you haven't found yet! this is a terrible way to do it, cpu and memory-wise..

Hans Henrik (Tue, 03/03/2015 - 16:28)

Permalink
if you're at all worried about cpu or memory, benchmark your code with this code http://stackoverflow.com/a/18853960/1067003function permute($arg) { $array = is_string($arg) ? str_split($arg) : $arg; if(1 === count($array)) return $array; $result = array(); foreach($array as $key => $item) foreach(permute(array_diff_key($array, array($key => $item))) as $p) $result[] = $item . $p; return $result; }also keep in mind that your algorithm will shuffle AT RANDOM, meaning the performance is not predictable, in fact, the performance can, and probably will, vary a lot between calls (with a big array), while performance of the code above is deterministic and predictable. (and probably a lot faster with big arrays)

Hans Henrik (Tue, 03/03/2015 - 16:34)

Permalink
You are right, it is terrible code. It's not elegant or performant and I have never used it in a production environment. In my defence I did write it 7 years ago!

Add new comment

The content of this field is kept private and will not be shown publicly.