生成没有重复字符的字符串排列

Question

我正在编写一个通用程序来生成字符串的排列，但要删除重复情况。为此，我使用了记忆化技术。

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

但结果并非如所期望，它打印出了所有的排列组合。有谁可以帮我找出问题所在。

- dead programmer

---

什么是“重复项”？ - Aniket Inge

你的意思是你想要组合而不是排列吗？ - chris

你尝试过使用std::next_permutation吗？ - Arunmu

对于那些问他所说的重复是什么意思的人，我认为他的意思是（给定输入“aab”）他不希望“aab”被返回两次（一次是原始字符串，再一次是当第一个和第二个 a 被排列时）。 - Cornstalks

Answer 1

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

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

- Grigor Gevorgyan

---

上面的原型不起作用。您能否使用codepad.org分享您的代码？ - dead programmer