Generating permutation of string without duplicates [duplicate]

Question

I have writing a general program to generate permutation of string but removing the duplicate cases . For this I am using memorization by using .

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

But the result is not as desired. It prints all the permutation. Can anyone help me in figuring out the problem.

To those asking what he means about duplicates, I assume he means (given input "aab") he doesn't want "aab" returned twice (once for the original string, and again when the first and second a are permuted). — Cornstalks
– Cornstalks, Commented Mar 22, 2013 at 5:18

Grigor Gevorgyan · Accepted Answer · 2013-03-22 09:34:31Z

3

First, you pass set<> s parameter by value, which discards your each insert, because it's done in the local copy of s only. However even if you change it to pass by reference, it won't work, because every time you insert the same char* value, so only one insert will be done. To make your code work correctly I suggest to change the prototype of your function to

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

and this works all right.

update: source code with described minor changes

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

edited Mar 22, 2013 at 9:34

answered Mar 22, 2013 at 6:10

Grigor Gevorgyan

6,8934 gold badges38 silver badges64 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

dead programmer Over a year ago

the above prototype is not working. Could you please share your code using codepad.org

Collectives™ on Stack Overflow

Generating permutation of string without duplicates [duplicate]

1 Answer 1

1 Comment

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Linked

Related