Tricky- permutation problem

#1

i know how to print the permutation but how can i print all the non same values of permuatation ?

#2

Hello,

If you are using recursive swapping approach for finding permutation,
Then I you should check if you should perform swapping or not.

Approach:
Permuatation(arr, indx, n){
For i= indx to n{
//Check if you should swap index with I or not

  1. If arr[i] is not present between index indx and i-1, then do swapping
  2. else if it is already present, then swapping will lead to duplicate permutation., Thus, don’t perform swapping.
    }
    }

Hope, this would help.
Give a like, if you are satisfied.

#3

no i could not understand
this is my code for all permutation

#include<bits/stdc++.h>
using namespace std;
bool permutation(string s,string chosen)
{
if(s.empty())
{
cout<<chosen<<endl;
}
else
{
for(int i=0;i<s.length();i++)
{
char c=s[i];
chosen+=c;
s.erase(i,1);
permutation(s,chosen);
s.insert(i,1,c);// this insert function puts the charcater in c to the ith index one(1) number of time where if anyelement is already there will shifted in right automatically
chosen.erase(chosen.length()-1,1);
}
}

}
int main()
{

string a,b;
cin>>a;

permutation(a," ");
return 0;

}

#4

what should i do with this code or howi implement it?

#5

I apologize for the late reply.
I have checked your code, the logic you have applied is correct for permutation with redundancy.

But as your code is not keeping track of actual input string and you are removing one element from the string every time you go for recursive call, thus I am not able to find any effective way to keep track of already printed strings or redundancy.
You can see this to understand what exactly i am talking about.

I have an approach but it would require extra space:

  1. Create a hash map,
  2. Every time the base condition satisfies, check if chosen is already present in map using find()
    if not, insert it into map and print chosen,
    else, return without printing anything.

Hope, this would help.

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.