我需要一个算法，可以返回一个字符串中所有字符的所有可能组合。
我已经尝试过：
$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;
}
// 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
aa。从技术上讲，它只应该显示aa。但是在这里它显示为aa aa。 - Shurvir Mori我的变体（同样适用于数组或字符串输入）
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_split和array_diff_key标准函数，但是这段代码片段是最小的，它仅使用一个输入参数实现了纯尾递归，并且与输入数据类型同构。
也许在与其他实现进行比较时，它会在基准测试中稍微落后一些（但对于几个字符字符串，其实际性能几乎与@codaddict的答案相同），但为什么我们不能将其视为具有自己优点的不同选择之一呢？
$arg中有多个相同的字母，则$result中的排列不是唯一的。 - Ben<?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
)
啊，是的，组合 = 顺序无关紧要。排列 = 顺序很重要。
所以嘿，嗨耶都是同一种组合，但是有三个不同的排列方式，如上所述。请注意，物品的规模增长非常快。它被称为阶乘，并且写作6！= 6 * 5 * 4 * 3 * 2 * 1 = 720个项目（对于6个字符的字符串）。一个10个字符的字符串将会有10！= 3628800个排列，这是一个非常大的数组。在这个例子中，它是3！= 3 * 2 * 1 = 6。
我的方法采用递归而非循环，请查看并给予反馈：
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");
我创建了一个简单的类，使用生成器来创建排列组合。这样，您可以遍历所有可能的组合而不会耗尽内存。
该类可以接受字符串或数组，并返回可用foreach迭代的Generator对象。
显然，字符串或数组越长，生成所有排列组合所需的时间就越长。
此代码已针对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";
}
$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);
n!个结果。对于长度为12个字符的输入字符串（无重复字符），大约有4.8亿个结果，需要约5 GB的内存。 - Chris Lercher