Permutations of string ABC are ABC, ACB, BAC, BCA, CBA, CAB
Recurcive program to genrate permutation of String [ ABC ]
******************* Program ***************************
/*
Time Complexity: O(n*n!)
This program prints unique permutation,
if there are no repeating character in string.
in case of duplicate chars it will print duplicate permutations.
*/
#include <iostream>
using namespace std;
void string_permutation(string str, int left, int right){
// terminating condition
if(left == right){
cout << str << endl;
return;
}
for(int itr = left ; itr <= right ; itr++){
swap(str[left],str[itr]);
string_permutation(str, left + 1, right );
swap(str[left], str[itr]); // BT
}
}
int main(){
string str = "ABC";
string_permutation(str, 0, str.size()-1);
return 0;
}
Call flow of string_permutation function:
>>[Entry Permute] ABC with 0:2
itr=0 ***
[1.Before Permute] swap A with A
left= 0 right=2
[2.Permute] ABC with 1:2
>>[Entry Permute] ABC with 1:2
itr=1 ***
[1.Before Permute] swap B with B
left= 1 right=2
[2.Permute] ABC with 2:2
>>[Entry Permute] ABC with 2:2
ABC
[3.After Permute] swap B with B
itr=2 ***
[1.Before Permute] swap B with C
left= 1 right=2
[2.Permute] ACB with 2:2
>>[Entry Permute] ACB with 2:2
ACB
[3.After Permute] swap C with B
[3.After Permute] swap A with A
--------------------------------
itr=1 ***
[1.Before Permute] swap A with B
left= 0 right=2
[2.Permute] BAC with 1:2
>>[Entry Permute] BAC with 1:2
itr=1 ***
[1.Before Permute] swap A with A
left= 1 right=2
[2.Permute] BAC with 2:2
>>[Entry Permute] BAC with 2:2
BAC
[3.After Permute] swap A with A
itr=2 ***
[1.Before Permute] swap A with C
left= 1 right=2
[2.Permute] BCA with 2:2
>>[Entry Permute] BCA with 2:2
BCA
[3.After Permute] swap C with A
[3.After Permute] swap B with A
--------------------------------
itr=2 ***
[1.Before Permute] swap A with C
left= 0 right=2
[2.Permute] CBA with 1:2
>>[Entry Permute] CBA with 1:2
itr=1 ***
[1.Before Permute] swap B with B
left= 1 right=2
[2.Permute] CBA with 2:2
>>[Entry Permute] CBA with 2:2
CBA
[3.After Permute] swap B with B
itr=2 ***
[1.Before Permute] swap B with A
left= 1 right=2
[2.Permute] CAB with 2:2
>>[Entry Permute] CAB with 2:2
CAB
[3.After Permute] swap A with B
[3.After Permute] swap C with A
----------------------------------------
Similar Problems :
1. Palindrome string permutations e.g. -> str = "aacdd" then adcda, dacad, dacad ...
2. String permutation using STL.next_permutation() function on sorted string.
3. With Given constraint Genrate string permutation. like permutations do not contain "AB" substring.
No comments:
Post a Comment