Get all permutations of a PHP array?
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.
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
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)
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)));
}
}
}