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

Question

我需要一个算法,它返回一个字符串中所有字符的所有可能组合.

我试过了:

$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.

Answer 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

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

PS: Downvoter,请解释一下你的位置.此代码使用附加str_split和array_diff_key标准函数,但此代码段是最小的,它只使用一个输入参数实现纯尾递归,并且它与输入数据类型是同构的.

与其他实现相比,它可能会失去一些基准(但实际上几乎与@ codaddict对几个字符串的答案相同),但为什么我们不能将它视为具有它的不同选择之一自己的优势？

Answer 3

我会将所有字符放在一个数组中,并编写一个递归函数,它将"删除"所有剩余的字符.如果数组为空,则为引用传递的数组.

<?php

$input = "hey";

function string_getpermutations($prefix, $characters, &$permutations)
{
    if (count($characters) == 1)
        $permutations[] = $prefix . array_pop($characters);
    else
    {
        for ($i = 0; $i < count($characters); $i++)
        {
            $tmp = $characters;
            unset($tmp[$i]);

            string_getpermutations($prefix . $characters[$i], array_values($tmp), $permutations);
        }
    }
}
$characters = array();
for ($i = 0; $i < strlen($input); $i++)
    $characters[] = $input[$i];
$permutations = array();

print_r($characters);
string_getpermutations("", $characters, $permutations);

print_r($permutations);

打印出来:

Array
(
    [0] => h
    [1] => e
    [2] => y
)
Array
(
    [0] => hey
    [1] => hye
    [2] => ehy
    [3] => eyh
    [4] => yhe
    [5] => yeh
)

啊,是的,组合=顺序无关紧要.排列=顺序确实很重要.

所以,嘿,是的,所有的组合都是一样的,但是提到了3个独立的排列.注意物品的规模上升得非常快.它叫做阶乘,写得像6!= 6*5*4*3*2*1 = 720项(6字符串).一个10个字符的字符串将是10!= 3628800已经排列,这是一个非常大的数组.在这个例子中它是3!= 3*2*1 = 6.