生成无重复的aabb字符串全排列问题求助（附PHP代码）

原代码处理无重复字符的字符串时工作正常，但遇到如"aabb"这类含重复字符的字符串时，会生成大量重复排列。核心原因是当交换相同字符时（比如第一个a和第二个a），后续递归会生成完全一致的排列，原逻辑没有针对这种情况做剪枝处理。

解决方案：递归层级剪枝（推荐高效方案） #

在递归的循环层级中，记录已经处理过的字符，遇到重复字符时跳过该次循环，避免重复递归生成相同排列。

修改后的代码：

<?php
function permute($str, $l, $r) 
{ 
    if ($l == $r) 
        echo $str. " "; 
    else
    { 
        $used = []; // 记录当前层级已处理的字符，避免重复
        for ($i = $l; $i <= $r; $i++) 
        { 
            // 跳过已处理过的相同字符
            if (in_array($str[$i], $used)) {
                continue;
            }
            $used[] = $str[$i];
            
            $str = swap($str, $l, $i); 
            permute($str, $l + 1, $r); 
            $str = swap($str, $l, $i); 
        }
    } 
} 

function swap($a, $i, $j) 
{ 
    $charArray = str_split($a); 
    $temp = $charArray[$i]; 
    $charArray[$i] = $charArray[$j]; 
    $charArray[$j] = $temp; 
    return implode($charArray); 
} 
  
$str = "aabb"; 
$n = strlen($str); 
permute($str, 0, $n - 1); 
?>

代码说明 #

• 新增$used数组，用于在当前递归层级中记录已经处理过的字符。
• 每次循环前检查当前字符是否已在$used中，若是则跳过，避免重复交换相同字符触发重复递归。
• 运行后会输出无重复的正确排列：aabb abab abba baab baba bbaa

可选方案：结果集去重（适合短字符串） #

如果不想修改递归逻辑，可以先收集所有排列到数组，再用array_unique去重后输出：

<?php
$results = [];

function permute($str, $l, $r, &$results) 
{ 
    if ($l == $r) 
        $results[] = $str; 
    else
    { 
        for ($i = $l; $i <= $r; $i++) 
        { 
            $str = swap($str, $l, $i); 
            permute($str, $l + 1, $r, $results); 
            $str = swap($str, $l, $i); 
        }
    } 
} 

function swap($a, $i, $j) 
{ 
    $charArray = str_split($a); 
    $temp = $charArray[$i]; 
    $charArray[$i] = $charArray[$j]; 
    $charArray[$j] = $temp; 
    return implode($charArray); 
} 
  
$str = "aabb"; 
$n = strlen($str); 
permute($str, 0, $n - 1, $results); 
// 去重并输出
$uniqueResults = array_unique($results);
echo implode(" ", $uniqueResults);
?>

这种方式先生成所有可能的排列（包括重复），再去重，适合短字符串，长字符串下效率不如剪枝方案。

内容的提问来源于stack exchange，提问作者Clinton Canarias