如何在 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：反对者，请解释您的立场。此代码使用了额外的 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
)

啊是的，
组合=顺序并不重要。
排列=顺序很重要。

所以嘿，hye yeh 都是相同的组合，但是如上所述有 3 种不同的排列。请注意，物品的规模增长得非常快。它叫做阶乘，写成 6！ = 6*5*4*3*2*1 = 720 项（对于 6 个字符的字符串）。 10 个字符的字符串将是 10！ = 已经有3628800个排列，这是一个非常大的数组。在本例中为 3！ = 3*2*1 = 6。

Answer 4

我的方法使用递归并且没有循环，请检查并提供反馈：

function permute($str,$index=0,$count=0)
{
    if($count == strlen($str)-$index)
        return;

    $str = rotate($str,$index);

    if($index==strlen($str)-2)//reached to the end, print it
    {
        echo $str."<br> ";//or keep it in an array
    }

    permute($str,$index+1);//rotate its children

    permute($str,$index,$count+1);//rotate itself
}

function rotate($str,$index)
{
    $tmp = $str[$index];
    $i=$index;
    for($i=$index+1;$i<strlen($str);$i++)
    {
        $str[$i-1] = $str[$i];
    }
    $str[$i-1] = $tmp;
    return $str;
}
permute("hey");

Answer 5

我创建了一个简单的类，它使用 生成器 来创建排列这样你就可以迭代所有可能的组合而不会耗尽内存。

该类可以采用字符串或数组，
并返回一个 Generator 对象，可以使用 foreach 对其进行迭代。

显然，字符串或数组越长，生成所有排列所需的时间就越长。

这是针对 PHP 7.4 构建的

class Permutation {

    /** @var string|array **/
    protected $permutationRoot;
    protected int $permutationLength;

    /**
     * @param $permutationRoot
     */
    protected function __construct( $permutationRoot ) {
        $this->permutationRoot = $permutationRoot;
        $this->permutationLength = is_array($permutationRoot)
            ? count($permutationRoot)
            : strlen($permutationRoot);
    }

    /**
     * @param string|array $permutationRoot
     *
     * @return \Generator
     */
    public static function resolve( $permutationRoot ): \Generator
    {
        $instance = new static($permutationRoot);

        return $instance->backTrack(
            $instance->permutationRoot,
            0,
             $instance->permutationLength,
         );
    }

    /**
     * @param string|array $permutation
     * @param int $index
     * @param int $length
     *
     * @return \Generator
     */
    protected function backTrack($permutation, int $index, int $length): \Generator
    {
        if ($index === $length) {
            yield $permutation;
        }

        for ($i = $index; $i < $length; $i++) {
            $this->swap($permutation, $index, $i);
            yield from $this->backTrack($permutation, $index + 1, $length);
            $this->swap($permutation, $index, $i); // backtrack.
        }
    }

    /**
     * @param $permutation
     * @param int $index
     * @param int $n
     *
     * @return void
     */
    protected function swap(&$permutation, int $index, int $n): void {
        $temp = $permutation[$index];
        $permutation[$index] = $permutation[$n];
        $permutation[$n] = $temp;
    }
}

// Test
foreach ( Permutation::resolve('hey') as $perm ) {
    echo $perm . "\n";
}

Answer 6

$sentence = "This is a cat";
$words = explode(" ", $sentence);
$num_words = count($words);
$uniqueWords = [];
for ($i = 0; $i < $num_words; $i++) {
    for ($j = $i; $j < $num_words; $j++) {
        $uniqueWord = '';
        for ($k = $i; $k <= $j; $k++) {
            $uniqueWord .= $words[$k] . ' ';
        }
        $uniqueWords[] = trim($uniqueWord);
    }
}

var_dump($uniqueWords);

这对我有用