Permute an array in PHP

I wrote this function recently when I could not find it in the PHP function list. Please provide any optimizations you discover!

function permute($array)
{
  $results = array();

  if (count($array) == 1)
  {
    $results[] = $array;
  }
  else
  {
    for ($i = 0; $i < count($array); $i++)
    {
      $first = array_shift($array);
      $subresults = permute($array);
      array_push($array, $first);
      foreach ($subresults as $subresult)
      {
        $results[] = array_merge(array($first), $subresult);
      }
    }
  }
  return $results;
}

assert(permute(array()) == array());
assert(permute(array(1)) == array(array(1)));
assert(permute(array(1,2)) == array(array(1,2),array(2,1)) ||
       permute(array(1,2)) == array(array(2,1),array(1,2)));
assert(count(permute(array(1,2,3)) == 6));
assert(count(permute(array(1,2,3,4)) == 24));

One thought on “Permute an array in PHP”

Leave a Reply

Your email address will not be published. Required fields are marked *