无重复的aabb置换

Question

日安！

我试图排列这个字符串"aabb"，如果我使用"abcd“，结果是正确的，没有重复，但如果我使用"aabb”作为我的字符串，我得到一个不正确的结果。

这应该是结果

['aabb', 'abab', 'abba', 'baab', 'baba', 'bbaa']

但我得到的结果却是重复的

[aabb aabb abab abba abba abab aabb aabb abab abba abba abab baab baba baab baba bbaa bbaa baba baab bbaa bbaa baba baab]

这是我的Php代码供您检查。

<?php
function permute($str, $l, $r) 
{ 
    if ($l == $r) 
        echo $str. "\n"; 
    else
    { 
        for ($i = $l; $i <= $r; $i++) 
        { 
            $str = swap($str, $l, $i); 
            permute($str, $l + 1, $r); 
            $str = swap($str, $l, $i); 
        }

    } 
} 

function swap($a, $i, $j) 
{ 
    $temp; 
    $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); 
?>

Answer 1

在回送之前，您必须记住并检查是否存在。

function permute_unique($str, $l = null, $r = null, &$memory = [])
{
    if ($r === null) {
        $l = 0;
        $r = strlen($str) - 1;
    }
    if ($l == $r) {
        // echo $str. "\n";
        if (!in_array($str, $memory)) {
            $memory[] = $str;
        }

    } else {
        for ($i = $l; $i <= $r; $i++) {
            $str = swap($str, $l, $i);
            permute_unique($str, $l + 1, $r, $memory);
            $str = swap($str, $l, $i);
        }

    }
    return $memory;
}

function swap($a, $i, $j)
{
    $charArray = str_split($a);
    $temp = $charArray[$i];
    $charArray[$i] = $charArray[$j];
    $charArray[$j] = $temp;
    return implode($charArray);
}

$str = "aabb";
print_r(permute_unique($str));