获取 PHP 数组的所有排列？

问题描述 投票：0回答：8

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

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

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

peter-paul-mary
peter-mary-paul
paul-peter-mary
paul-mary-peter
mary-peter-paul
mary-paul-peter
php permutation combinatorics
8个回答
26
投票
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

12
投票

这可以满足您的需要，即无需分配任何额外的内存。它将结果排列存储在 $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。我使用匿名函数进行递归，以保持主函数的界面干净。

9
投票

我需要类似的东西，在寻找时发现了这篇文章。写了以下内容来完成这项工作。

对于 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)));
        }
    }
}
7
投票

我对杰克的答案进行了一些扩展

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

我发现返回数组而不是字符串更有用。然后由使用应用程序如何处理结果（加入它们，或其他）

4
投票

带有递归且没有人为额外参数的简单版本：

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

这个算法很好，对你在纸上的做法很有启发，但在其他方面效率非常低，因为它多次计算相同的排列。更不用说，随着计算空间和数量呈指数级增长，计算较大数组的排列是非常不切实际的。

1
投票

递归函数获取数组的所有排列。

调用 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;
}
0
投票

这是基于本文的另一个变体：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
    )
)
0
投票

这是一个可读、易于理解的递归解决方案，使用易于记忆和视觉验证的方法。

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;
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.