36

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

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

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

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

6 回答 6

24 
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

于 2012-04-19T07:02:17.873 回答
11

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

于 2014-07-01T19:34:01.210 回答
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个有1​​20个，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)));
        }
    }
}
于 2012-10-05T16:01:37.260 回答
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;
}

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

于 2016-12-21T07:25:21.167 回答
4

我对杰克的回答做了一些扩展

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

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

于 2016-04-21T11:23:56.920 回答
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
    )
)
于 2021-08-24T14:28:17.700 回答