Getting All Permutations Of An Array In PHP

Friday, February 29, 2008 - 10:59

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
$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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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;
}
Category: 
philipnorton42's picture

Philip Norton

Phil is the founder and administrator of #! code and is an IT professional working in the North West of the UK.
Google+ | Twitter

Comments

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

if you're at all worried about cpu or memory, benchmark your code with this code http://stackoverflow.com/a/18853960/1067003
1
2
3
4
5
6
7
8
9
10
function 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)
philipnorton42's picture
Submitted by philipnorton42 on Tue, 03/03/2015 - 17:42

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