字符串的C++递归排列算法 - >不跳过重复

Question

我找不到一个简单的语句来跳过这个递归排列代码的重复项.我到处看,似乎只找到使用swap或java的例子.从我收集的内容来看,我认为我需要在for-loop之后放一条线.

谢谢!

#include "genlib.h"
#include "simpio.h"
#include <string>
#include <iostream>

void ListPermutations(string prefix, string rest);


int main() {

    cout << "Enter some letters to list permutations: ";
    string str = GetLine();
    cout << endl << "The permutations are: " << endl;
    ListPermutations("", str);

    return 0;
}

void ListPermutations(string prefix, string rest)
{
    if (rest == "") 
    {
        cout << prefix << endl;
    } 
    else 
    {   
        for (int i = 0; i < rest.length(); i++) 
        {
            if (prefix != "" && !prefix[i]) continue; // <--- I tried adding this, but it doesn't work
            cout << endl<< "prefix: " << prefix << " | rest: " << rest << endl;     
            string newPrefix = prefix + rest[i];
            string newRest = rest.substr(0, i) + rest.substr(i+1);  
            ListPermutations(newPrefix, newRest);           
        }    
    }
}

Answer 1

这应该工作:你的算法很好,我只添加了一个测试:如果一个位置已经使用了一个独特的字符.如果是,则不再进行排列,因为已经在该位置使用该字符的所有排列.

void ListPermutations(string prefix, string rest)
{
if (rest == "") 
{
    cout << prefix << endl;
} 
else 
{   
    for (int i = 0; i < rest.length(); i++) 
    {


        //test if rest[i] is unique.
        bool found = false;
        for (int j = 0; j < i; j++) 
        {
            if (rest[j] == rest[i])
                found = true;
        }
        if(found)
            continue;
        string newPrefix = prefix + rest[i];
        string newRest = rest.substr(0, i) + rest.substr(i+1);  
        ListPermutations(newPrefix, newRest);           
    }    
}
}

您也可以在进行排列之前对字符串进行排序,结果将是相同的.