c++ - 生成没有重复的字符串置换[duplicate]

This question already has answers here:

Finding all the unique permutations of a string without generating duplicates

(5个答案)


7年前关闭。




我已经编写了一个通用程序来生成字符串排列，但删除了重复的情况。为此，我使用来进行记忆。

void permute(char *a,int i, int n,set<char*> s)
{
    if(i==n)
    {
        if(s.find(a)==s.end()){
            cout<<"no dublicate"<<endl;
            cout<<a<<endl;
            s.insert(a)
        }
    }
    else{
        for(int j=i;j<n;j++)
        {
            swap(a[i],a[j]);
            permute(a,i+1,n,s);
            swap(a[i],a[j]);
        }
    }
}

int main()
{
    char a[]="aba";
    set <char*> s;
    permute(a,0,3,s);
    return 0;
}

但是结果并不理想。它打印所有排列。谁能帮助我解决问题。

最佳答案

首先，您按值传递set<> s参数，该参数会丢弃您的每个插入内容，因为它仅在s的本地副本中完成。但是，即使将其更改为通过引用传递，也将无法使用，因为每次您插入相同的char *值时，都只会执行一次插入。为了使您的代码正常工作，我建议将函数原型(prototype)更改为

void permute(string a,int i, int n,set<string>& s)

这行得通。

更新:源代码，其中描述了较小的更改

void permute(string a,int i, int n,set<string>& s)
{
    if(i==n)
    {
        if(s.find(a)==s.end()){
            cout<<"no dublicate"<<endl;
            cout<<a<<endl;
            s.insert(a);
        }
    }
    else{
        for(int j=i;j<n;j++)
        {
            swap(a[i],a[j]);
            permute(a,i+1,n,s);
            swap(a[i],a[j]);
        }
    }
}

int main()
{
    string a ="aba";
    set <string> s;
    permute(a,0,3,s);
    return 0;
}