如何在PHP中生成字符串的所有排列？

php string algorithm permutation combinations

2022-08-30 11:50:30

我需要一个算法，在一个字符串中返回所有字符的所有可能组合。

我试过了：

$langd = strlen($input);
 for($i = 0;$i < $langd; $i++){
     $tempStrang = NULL;
     $tempStrang .= substr($input, $i, 1);
  for($j = $i+1, $k=0; $k < $langd; $k++, $j++){
   if($j > $langd) $j = 0;
   $tempStrang .= substr($input, $j, 1);
 }
 $myarray[] = $tempStrang;
}

但这只返回与字符串长度相同的数量组合。

假设，结果将是：。$input = "hey"hey, hye, eyh, ehy, yhe, yeh

答案 1

您可以使用基于回溯跟踪的方法来系统地生成所有排列：

// function to generate and print all N! permutations of $str. (N = strlen($str)).
function permute($str,$i,$n) {
   if ($i == $n)
       print "$str\n";
   else {
        for ($j = $i; $j < $n; $j++) {
          swap($str,$i,$j);
          permute($str, $i+1, $n);
          swap($str,$i,$j); // backtrack.
       }
   }
}

// function to swap the char at pos $i and $j of $str.
function swap(&$str,$i,$j) {
    $temp = $str[$i];
    $str[$i] = $str[$j];
    $str[$j] = $temp;
}   

$str = "hey";
permute($str,0,strlen($str)); // call the function.

输出：

#php a.php
hey
hye
ehy
eyh
yeh
yhe

答案 2

我的变体（也适用于数组或字符串输入）

function permute($arg) {
    $array = is_string($arg) ? str_split($arg) : $arg;
    if(1 === count($array))
        return $array;
    $result = array();
    foreach($array as $key => $item)
        foreach(permute(array_diff_key($array, array($key => $item))) as $p)
            $result[] = $item . $p;
    return $result;
}

附言：投下士，请解释你的立场。此代码使用其他标准函数，但此代码段是最小的，它仅使用一个输入参数实现纯尾递归，并且与输入数据类型同构。str_splitarray_diff_key

也许与其他实现相比，它会稍微失去基准测试（但性能实际上与@codaddict对几个字符串的答案几乎相同），但是为什么我们不能将其视为具有自身优势的不同替代方案之一？