Good Day!

I was trying to permutation this string "aabb", if I use "abcd" the result was correct and no duplicate but if I use "aabb" as my string I got an incorrect result.

This should be the result

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

But instead I got this result it has duplicates

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

Heres my Php code for your checking.

<?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); 
?>

CodePudding user response：

You will have to remember and check if exists before you echo.

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));