Как я могу удалить дублированную перестановку этого кода?

Question

Я пытаюсь сгенерировать перестановки строки. Этот код работает нормально, но когда символ повторяется, печатается повторяющаяся перестановка. Пример приведен ниже.

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

Введите:

aab

Выход:

aab
aba
aab
aba
baa
baa

Answer 1

В вашей программе для каждой позиции start вы запускаете цикл for до длины строки. Если строка содержит повторяющиеся символы, она будет отображаться несколько раз. Это вызывает повторные перестановки. Таким образом, вы должны убедиться, что один и тот же символ не появляется для определенной позиции start несколько раз. Вы можете сделать это, используя дополнительный массив isCharUsed, чтобы отслеживать, используется ли символ раньше. Мое решение дано ниже:

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

Введите:

aab

Выход:

aab
aba
baa