Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 3 down vote favorite
1

I'm having trouble finding a simple statement to skip the duplicates for this recursive permutation code. I've looked everywhere and seem to only find examples using swap or java. From what I gather, I think I need to put a line right after the for-loop.

Thank you!

#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);           
        }    
    }
}
share|improve this question
I have the strong feeling that you can generate them in such a way that the duplicates won't be emitted in the first place. However, my brain is on malfunctino right now and I can't seem to visualize it right now – sehe Nov 6 '11 at 20:17
1  
@sehe - see my answer below - you just need to invoke sort on the str before starting and only recurse once for each unique char in rest. The sorting might not even be necessary... but I can't get my head around whether it would work without it right now – je4d Nov 6 '11 at 21:49

3 Answers

up vote 6 down vote accepted

this should work : your algoithm is good, i only added a test : if a unique char is already used at a position. if yes, no more permutation is made because all permutations with that char in that position is already made.

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

you can also sort the string before making permutations, the result will be the same.

share|improve this answer
thank you so much, that is awesome it never occurred to me to add another for loop...! – OverAir Nov 7 '11 at 1:43
up vote 3 down vote

In C++ to generate permutation use std::next_permutation

It will handle duplicate entries just fine and do the right thing

share|improve this answer
Thank you, but is there another way using boolean logic or something else? thank you, sorry for not specifying homework earlier. – OverAir Nov 6 '11 at 20:10
To skip duplicates you might have to modify the code to maintain each character and its current count. The recursive function will use a character and lowers its count and call itself. – parapura rajkumar Nov 6 '11 at 20:16
up vote 1 down vote

Ignoring the availability of std::next_permutation, because your comment on the previous answer...

If you want to generate all the unique permutations, you're going to need to have them in order at some point. The hackiest way to do this would be to put them all in a vector, sort it and then suppress duplicate adjacent entries when printing it out. But that's a lot slower than it needs to be.

You'll need to start with by sorting your string, so that identical permutations will be generated after each other. Then in your for loop, make sure you skip any duplicate letters in 'rest'. something like:

    char lastAdditionToPrefix = '\0';
    for (int i = 0; i < rest.length(); i++) 
    {
        if (rest[i] == lastAdditionToPrefix) continue;
        lastAdditionToPrefix = rest[i];
        cout << endl<< "prefix: " << prefix << " | rest: " << rest << endl;     
        ...

I'm not convinced that this change will completely fix your code, but it's closer than you are at the moment. edit: this, plus sorting the input in main(), will work

share|improve this answer
thank you, vector would be slower indeed. My feeling is that it has something to do with comparing prefix to rest and skip the next recursion or increment i? my brain just explodes when I try to work it out... – OverAir Nov 6 '11 at 20:56
I don't think you need to compare prefix to rest at all - you just need to make sure that your function only calls itself once for each unique character in 'rest'. The code in my answer should do that because 'rest' will always be sorted if the initial string was sorted (which it isn't in your example, you need to invoke std::sort on str in main so it is) – je4d Nov 6 '11 at 21:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.