CODEWITHSUNDEEP
c++stringrecursionpermutation
OverAir
OverAir

Reputation: 173

C++ recursive permutation algorithm for strings -> not skipping duplicates

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

Upvotes: 3

Views: 8313

Answers (5)

Will Yu
Will Yu

Reputation: 552

The different for algorithms with or without duplicate would be when you swap it, make sure that the character that you want to swap has not been swapped before. Use hash map to keep track of what you have swapped before.

See the C# code below.

    private void PermuteUniqueHelper(int[] nums, int index, List<IList<int>> res)
    {
        var used = new Dictionary<int, bool>();
        if (index == nums.Length)
        {
            res.Add(new List<int>(nums));
            return;
        }

        for (int i = index; i < nums.Length; i++)
        {
            if (!used.ContainsKey(nums[i]))
            {
                swap(nums[i], nums[index]);

                this.PermuteUniqueHelper(nums, index + 1, res);

                swap(nums[i], nums[index]);

                used.Add(nums[i], true);
            }
        }
    }

Upvotes: 0

Haoru HE
Haoru HE

Reputation: 21

Tested and works fine. The idea is for each stack level, at location i, remember whether a character has been at that location already.

using namespace std;

void doPermutation(vector<char> &input, int index) {
    bool used[26] = {false};

    if(index == input.size()) {
        copy(input.begin(), input.end(), ostream_iterator<char>(cout, "") );
        cout << endl;

    } else {
      int i, j;
      for(i =index; i < input.size(); i++ ) {
        if(used[ input[i]-'a'] == false) {
           swap(input[i], input[index]);
           doPermutation(input, index+1);
           swap(input[i], input[index]);
           used[input[i]-'a'] = true;
       } 
      }
    }
}

  void permutation(vector<char>& input) {
      doPermutation(input, 0);
  }


int main()
{
   cout << "Hello World" << endl; 
   const char* inp = "alla";
   vector<char> input(inp, inp + 4 );

   permutation(input);

   return 0;
}

Upvotes: 0

Hicham
Hicham

Reputation: 979

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.

Upvotes: 8

je4d
je4d

Reputation: 7838

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

Upvotes: 1

parapura rajkumar
parapura rajkumar

Reputation: 24403

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

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

Upvotes: 4

Related Questions