获取PHP数组的所有排列组合？

Question

给定一个 PHP 字符串数组，例如：

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

如何生成该数组元素的所有可能排列？例如：

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

- ohho

---

你需要它做什么？ 这太贵了，我觉得... 必须有更聪明的选择... - Andreyco

这是一个具有指数运行时间的操作。当数组中有10个元素时，您将会得到成千上万个排列组合。当它达到20时，您可能已经超过了百万级别。 - GordonM

我认为你的意思是排列而不是组合。 - Jack

@Andreyco 检查一个包含三个字段的网页表单是否存在于单列表中。 - ohho

重复链接 https://dev59.com/Am035IYBdhLWcg3wSOGr - Titus

根据您的示例输出，您所要求的是组合而不是排列。 - Kuya

Answer 1

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

或者

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

- Jack

---

我最终使用了 pc_next_permutation() 来获得更好的返回类型。谢谢！ - ohho

Answer 2

这个函数可以在原地完成你需要的操作，即不需要分配任何额外的内存。它将结果排列储存在 $results 数组中。我非常有信心说这是解决该任务的最快方法。

<?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);

这在PHP>5.4中有效。我使用了一个匿名函数进行递归，以保持主函数的接口整洁。

- MaximeW

Answer 3

我需要类似的东西，并在搜索时发现了这篇文章。最终编写了以下代码，可以完成此任务。

当有8项时，它的工作速度相当快（比我在网上找到的例子稍微快一些），但超过这个数量后，运行时间会迅速增加。如果您只需要输出结果，则可以使其更快，并大大减少内存使用。

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

请注意，排列的数量是数组中项目数的阶乘。对于3个项目，有6种排列方式；对于4个项目，有24种排列方式；对于5个项目，有120种排列方式；对于6个项目，有720种排列方式，以此类推。

编辑

回来看了一下，做了一些修订。

下面是这个函数的改进版本，它使用更少的存储空间并且更快（比我见过的其他解决方案更快）。

它将返回的数组作为参数传递，并通过引用传递它。这减少了数据重复的量，因为它运行时会经过。

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

- Kickstart

Answer 4

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

这将实际返回包含所有可能排列的数组。

$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

我发现返回一个数组比返回一个字符串更有用。这样，使用该应用程序可以自行处理结果（将它们连接起来或其他操作）。

- Tschallacka

Answer 5

使用递归和没有人为额外参数的简单版本：

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

这个算法在纸上执行起来很好理解，但是在实际中效率非常低下，因为它会多次计算相同的排列。而且，在处理较大数组的排列时，它非常不实用，因为所需空间和计算量呈指数级增长。

- baa2w

---

最佳解决方案，因为此方法不会干扰输入中的重复值。因此，像“1”，“1”，“2”这样的输入将生成所需的输出。 - Spears

Answer 6

一个递归函数，用于获取数组的所有排列组合。

调用getPermutations($arr)可以获取包含所有排列组合的数组。

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

- Agustí Pons

Answer 7

这是基于这篇文章的另一种变体：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;
}

例子：

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

输出：

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

- Sergio Zaharchenko

Answer 8

这是一个可读性强、容易理解的递归解决方案，使用一种方法，通过视觉验证后容易记住。

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

- Matthew Slyman