Get all permutations of a PHP array?

Question

Given a PHP array of strings, e.g.:

['peter', 'paul', 'mary']

How to generate all possible permutations of elements of this array? i.e.:

peter-paul-mary
peter-mary-paul
paul-peter-mary
paul-mary-peter
mary-peter-paul
mary-paul-peter

Answer 1

Simple version with recursion and no artificial extra arguments:

function permuteArray(array $input) {
    $input = array_values($input);

    // permutation of 1 value is the same value
    if (count($input) === 1) {
        return array($input);
    }

    // to permute multiple values, pick a value to put in the front and 
    // permute the rest; repeat this with all values of the original array
    $result = [];
    for ($i = 0; $i < count($input); $i++) {
        $copy  = $input;
        $value = array_splice($copy, $i, 1);
        foreach (permuteArray($copy) as $permutation) {
            array_unshift($permutation, $value[0]);
            $result[] = $permutation;
        }
    }

    return $result;
}

This algorithm is nice and instructive how you would do it on paper, but otherwise very inefficient as it calculates same permutations multiple times. Not to mention that it is very impractical for calculating permutations of larger arrays as the space and number of calculations grow exponentially.

Answer 2

Here is a readable, readily understandable recursive solution using a method that is easy to remember and validate by sight.

function permutations(array $arr):array{
    switch(\count($arr)){
    case 0:return [];
    case 1:return [$arr];
    default:
        $result=[];
        foreach($arr AS $i => $elem){
            foreach(permutations(arr_without_element($arr,$i)) AS $perm){
                $result[]=\array_merge([$elem],$perm);
            }
        }
        return $result;
    }
}
function arr_without_element(array $arr, int $idx){
    if(\count($arr)===0){
        throw new \Exception('Cannot remove element from array of zero length!');
    }
    \array_splice($arr, $idx, 1, []);
    return $arr;
}

Answer 3

Recursive function to get all permutations of an array.

Call getPermutations($arr) to get an array of arrays with all the permutations.

function getPermutations ($arr)
{
    assert (!empty($arr));

    if (count($arr)==1)
    {
        return [$arr];
    }

    $first=array_shift($arr);
    $permutations=getPermutations($arr);
    $result=[];
    foreach ($permutations as $permutation)
    {
        $result=array_merge($result, addElementInAllPositions($permutation, $first));
    }
    return $result;
}

function addElementInAllPositions ($arr, $element)
{
    $i=0;
    $result=[];
    while ($i<=count($arr))
    {
        $result[]=array_merge(array_slice($arr,0,$i), [$element], array_slice($arr, $i));
        $i++;
    }
    return $result;
}

Answer 4

Here is another variant based on this article: https://docstore.mik.ua/orelly/webprog/pcook/ch04_26.htm

public static function get_array_orders( $arr ) {
    $arr    = array_values( $arr ); // Make sure array begins from 0.
    $size   = count( $arr ) - 1;
    $order  = range( 0, $size );
    $i      = 0;
    $orders = [];
    do {
        foreach ( $order as $key ) {
            $orders[ $i ][] = $arr[ $key ];
        }

        $i ++;
    } while ( $order = self::get_next_array_order( $order, $size ) );

    return $orders;
}


protected static function get_next_array_order( $order, $size ) {
    // slide down the array looking for where we're smaller than the next guy
    $i = $size - 1;
    while ( isset( $order[ $i ] ) && $order[ $i ] >= $order[ $i + 1 ] ) {
        $i --;
    }

    // if this doesn't occur, we've finished our permutations, the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1)
    if ( $i == - 1 ) {
        return false;
    }

    // slide down the array looking for a bigger number than what we found before
    $j = $size;

    while( $order[ $j ] <= $order[ $i ] ){
        $j--;
    }

    // swap them
    $tmp         = $order[ $i ];
    $order[ $i ] = $order[ $j ];
    $order[ $j ] = $tmp;

    // now reverse the elements in between by swapping the ends
    for ( ++ $i, $j = $size; $i < $j; ++ $i, -- $j ) {
        $tmp     = $order[ $i ];
        $order[ $i ] = $order[ $j ];
        $order[ $j ] = $tmp;
    }

    return $order;
}

Example:

$langs  = ['en', 'fr', 'ru'];
$orders = self::get_array_orders( $langs );
print_r($orders);

Outputs:

Array (

 [0] => Array
    (
        [0] => en
        [1] => fr
        [2] => ru
    )

 [1] => Array
    (
        [0] => en
        [1] => ru
        [2] => fr
    )

 [2] => Array
    (
        [0] => fr
        [1] => en
        [2] => ru
    )

 [3] => Array
    (
        [0] => fr
        [1] => ru
        [2] => en
    )

 [4] => Array
    (
        [0] => ru
        [1] => en
        [2] => fr
    )

 [5] => Array
    (
        [0] => ru
        [1] => fr
        [2] => en
    )
)

Answer 5

I needed something similar and found this post while looking. Landed up writing the following which does the job.

With 8 items it works fairly quickly (a bit quicker than the examples I found online), but go beyond that and the run time ramps up rapidly. If you only need to output the results it could be made quicker and the memory use reduced massively.

print_r(AllPermutations(array('peter', 'paul', 'mary')));

function AllPermutations($InArray, $InProcessedArray = array())
{
    $ReturnArray = array();
    foreach($InArray as $Key=>$value)
    {
        $CopyArray = $InProcessedArray;
        $CopyArray[$Key] = $value;
        $TempArray = array_diff_key($InArray, $CopyArray);
        if (count($TempArray) == 0)
        {
            $ReturnArray[] = $CopyArray;
        }
        else
        {
            $ReturnArray = array_merge($ReturnArray, AllPermutations($TempArray, $CopyArray));
        }
    }
    return $ReturnArray;
}

Note that the number of permutations is the factorial of the number of items in the array. For 3 items there are 6 permutations, for 4 there are 24, for 5 there are 120, for 6 there are 720, etc.

EDIT

Came back to have a look at this and done some revisions.

Below is an improved version of this function, which uses less storage and is quicker (quicker than other solutions I have seen).

It takes the return array as a parameter, passing it through by reference. This reduces the amount of duplication of data as it runs through.

function AllPermutations($InArray, &$ReturnArray = array(), $InProcessedArray = array())
{
    if (count($InArray) == 1)
    {
        $ReturnArray[] = array_merge($InProcessedArray, $InArray);
    }
    else
    {
        foreach($InArray as $Key=>$value)
        {
            $CopyArray = $InArray;
            unset($CopyArray[$Key]);
            AllPermutations2($CopyArray, $ReturnArray, array_merge($InProcessedArray, array($Key=>$value)));
        }
    }
}

Answer 6

function pc_permute($items, $perms = array()) {
    if (empty($items)) { 
        echo join(' ', $perms) . "<br />";
    } else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
             list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             pc_permute($newitems, $newperms);
         }
    }
}

$arr = array('peter', 'paul', 'mary');

pc_permute($arr);

or

function pc_next_permutation($p, $size) {
    // slide down the array looking for where we're smaller than the next guy
    for ($i = $size - 1; $p[$i] >= $p[$i+1]; --$i) { }

    // if this doesn't occur, we've finished our permutations
    // the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1)
    if ($i == -1) { return false; }

    // slide down the array looking for a bigger number than what we found before
    for ($j = $size; $p[$j] <= $p[$i]; --$j) { }

    // swap them
    $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;

    // now reverse the elements in between by swapping the ends
    for (++$i, $j = $size; $i < $j; ++$i, --$j) {
         $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
    }

    return $p;
}

$set = split(' ', 'she sells seashells'); // like array('she', 'sells', 'seashells')
$size = count($set) - 1;
$perm = range(0, $size);
$j = 0;

do { 
     foreach ($perm as $i) { $perms[$j][] = $set[$i]; }
} while ($perm = pc_next_permutation($perm, $size) and ++$j);

foreach ($perms as $p) {
    print join(' ', $p) . "\n";
}

http://docstore.mik.ua/orelly/webprog/pcook/ch04_26.htm

Answer 7

This does what you need, in place, i.e. without allocating any additional memory. It stores the resulting permutations the $results array. I am pretty confident that this is the fasted way to solve the task.

<?php
function computePermutations($array) {
    $result = [];

    $recurse = function($array, $start_i = 0) use (&$result, &$recurse) {
        if ($start_i === count($array)-1) {
            array_push($result, $array);
        }

        for ($i = $start_i; $i < count($array); $i++) {
            //Swap array value at $i and $start_i
            $t = $array[$i]; $array[$i] = $array[$start_i]; $array[$start_i] = $t;

            //Recurse
            $recurse($array, $start_i + 1);

            //Restore old order
            $t = $array[$i]; $array[$i] = $array[$start_i]; $array[$start_i] = $t;
        }
    };

    $recurse($array);

    return $result;
}


$results = computePermutations(array('foo', 'bar', 'baz'));
print_r($results);

This works in PHP>5.4. I used a anonymous function for recursion to keep the main function's interface clean.

Answer 8

I expanded a bit on the answer of Jack

function pc_permute($items, $perms = [],&$ret = []) {
   if (empty($items)) {
       $ret[] = $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);
           $this->pc_permute($newitems, $newperms,$ret);
       }
   }
   return $ret;
}

This will actually return an array with all possible permutations.

$options = ['startx','starty','startz','endx','endy','endz'];
$x = $this->pc_permute($options);
var_dump($x);

  [0]=>
 array(6) {
    [0]=>
    string(6) "startx"
    [1]=>
    string(6) "starty"
    [2]=>
    string(6) "startz"
    [3]=>
    string(4) "endx"
    [4]=>
    string(4) "endy"
    [5]=>
    string(4) "endz"
  }
  [1]=>
  array(6) {
    [0]=>
    string(6) "starty"
    [1]=>
    string(6) "startx"
    [2]=>
    string(6) "startz"
    [3]=>
    string(4) "endx"
    [4]=>
    string(4) "endy"
    [5]=>
    string(4) "endz"
  }
  [2]=>
  array(6) {
    [0]=>
    string(6) "startx"
    [1]=>
    string(6) "startz"
    [2]=>
    string(6) "starty"
    [3]=>
    string(4) "endx"
    [4]=>
    string(4) "endy"
    [5]=>
    string(4) "endz"
  }
  [3]=>
  array(6) {
    [0]=>
    string(6) "startz"
    [1]=>
    string(6) "startx"
    [2]=>
    string(6) "starty"
    [3]=>
    string(4) "endx"
    [4]=>
    string(4) "endy"
    [5]=>
    string(4) "endz"
  }
  [4]=>
  array(6) {
    [0]=>
    string(6) "starty"
    [1]=>
    string(6) "startz"
    [2]=>
    string(6) "startx"
    [3]=>
    string(4) "endx"
    [4]=>
    string(4) "endy"
    [5]=>
    string(4) "endz"
  }
  [5]=>
  array(6) {
    [0]=>
    string(6) "startz"
    [1]=>
    string(6) "starty"
    [2]=>
    string(6) "startx"
    [3]=>
    string(4) "endx"
    [4]=>
    string(4) "endy"
    [5]=>
    string(4) "endz"
  }
  [6]=> ................ a lot more

I found it a bit more usefull to get an array back instead of a string. Then it's up to the using application how to handle the resutls(to join them, or something else)