A permutation is an act of rearranging or reordering elements of a set or string uniquely etc.
For n elements, n! (n factorial) permutations are possible if there is no repetition.
For n elements, permutations are possible, where ak represents the occurrence of the kth character in the string.
Ex-> Possible permutations of aabc is = 4!/2! = 12.
abac abca aabc aacb acab acba baac baca bcaa cbaa caba caab
Before solving this question, please refer to this question.
Algorithm
Everything is the same just like this question, except now we can have duplicates too. To avoid duplication we have to make sure that we don’t repeat the selection of a character.
We have to check before considering a character whether it is repeated or not.
can_swap(str, start, i){ for(j=start; j<i; j++){ if(str[j]==str[i] return false; return true; } find_permutation(str, start, end){ if(start == end) print(str) for(i=start; i<end; i++){ if(can_swap(str, start,i)==true){ swap(str[start], str[i]); //we fixed the ith index and now in next recursion //we will work with the remaining string elements find_permutation(str, start+1, end); swap(str[i], str[start]); } } return 0; }
Implementation of the above algorithm in CPP
#include <bits/stdc++.h>
using namespace std;
bool can_swap(string str, int start, int i){
for(int j=start;j<i;j++){
if(str[i]==str[j])
return false;
}
return true;
}
int find_permutation(string str, int start, int end){
if(start==end)
cout<<str<<endl;
for(int i=start; i<end; i++){
if(can_swap(str, start, i)){
swap(str[start],str[i]);
find_permutation(str, start+1,end);
swap(str[start],str[i]);
}
}
return 0;
}
int main()
{
string str = "abac";
find_permutation(str, 0, str.size());
return 0;
}
Output
abac abca aabc aacb acab acba baac baca bcaa cbaa caba caab