How can I remove a duplicated permutation of this code?

Question

I am trying to generate the permutations of a string. This code is working fine, but when a char is repeated, a duplicate permutation is printed. Example is given below.

string s;
int num[50], used[50], cur[50];

void permute(int start, int len)
{
    if(start == len)
    {
        for(int i = 0; i < len; i++)
            printf("%c", s[num[i]]);
        printf("\n");
        return;

    }

    for(int i = 0; i < len; i++)
    {

        if(used[i] == 0)
        {
            used[i] = 1;
            num[start] = i;
            permute(start+1, len);
            used[i] = 0;
        }
    }
}

Input:

aab

Output:

aab
aba
aab
aba
baa
baa

One easy solution would be to remember all printed strings. After generating a new permutation, search in the remembered string list. If it is found, don't print it. — Donotalo, Oct 29 '18 at 06:40
@Donotalo I already trying this way, But i get TLE in some problems. — Milon Mahato, Oct 29 '18 at 06:48
@macroland I'm trying this but getting TLE :( . any efficient way? — Milon Mahato, Oct 29 '18 at 06:57
The time complexity of search and insert for std::set or std::map is O(log n) — macroland, Oct 29 '18 at 07:53
You may find your solution here: http://wordaligned.org/articles/next-permutation — Donotalo, Oct 29 '18 at 09:09
Possible duplicate of [Algorithm to list unique permutations of string with duplicate letters](https://stackoverflow.com/questions/40752319/algorithm-to-list-unique-permutations-of-string-with-duplicate-letters) — Matt Timmermans, Oct 29 '18 at 12:44

score 1 · Accepted Answer · answered Oct 29 '18 at 16:53

In your program, for each start position you ran a for loop up to the length of the string. If the string contains duplicate characters, then it will appear for multiple times. This causes duplicate permutations. So you have to make sure that same character does not appear for a specific start position for multiple times. You can do this using an additional array isCharUsed to keep track of whether is character is used before. My solution is given below:

string s;
int num[50], used[50], cur[50];

void permute(int start, int len)
{
    if(start == len)
    {
        for(int i = 0; i < len; i++)
            printf("%c", s[num[i]]);
        printf("\n");
        return;

    }

    // to keep track whether this character used before or not
    bool isCharUsed[27] = {0};

    for(int i = 0; i < len; i++)
    {

        if(used[i] == 0 && isCharUsed[s[i]-'a'] == false)
        {
            // set true for this character, so that it does not appear again
            isCharUsed[s[i]-'a'] = true;

            used[i] = 1;
            num[start] = i;
            permute(start+1, len);
            used[i] = 0;
        }
    }
}

Input:

aab

Output:

aab
aba
baa

How can I remove a duplicated permutation of this code?

1 Answers1