Home Practice Programming Print all permutations of a string with unique characters

Print all permutations of a string with unique characters

A permutation is an act of rearranging or reordering elements of a set or string etc.
For n elements, n! (n factorial) permutations are possible.
Ex-> Possible permutations of abc are abc, acb, bac, bca, cab, cba.

Here, given a string with n elements, we have to generate all possible permutation of this string.

Algorithm

  1. Start with the original string str and call the function find_permuation() with parameters original string, start index(0) and end index(str.size()-1).
  2. Iterate through every element of the string and perform the following operation i.e, for(i in range start to end-1).
  3. For every ith element of the string swap it with the 0th element, i.e, swap(str[start],str[i])
  4. Fix the current element, and again call the find_permuatation() function with parameters: the updated string, start index = current start index + 1 and original end index i.e, find_permuatation(str, start+1, end);
  5. After the current recursion terminates, re-swap the ith index with the 0th index i.e., swap(str[i],str[start])
  6. If start ==  end, we have reached the end of the recursion and found the permutation, print it and return
  7. Repeat step 2 to step 6 for every string element.

find_permutation(str, start, end){
    if(start == end)
        print(str)
    for i in range [start to end){
        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;

int find_permutation(string str, int start, int end){

	if(start==end) 
		cout<<str<<endl;

	for(int i=start; i<end; i++){
		swap(str[start],str[i]);
		find_permutation(str, start+1,end);
		swap(str[start],str[i]);
	}
	return 0;
}

int main()
{
	string str = "abc";
	find_permutation(str, 0, str.size());
	
	return 0;
}

Output

abc
acb
bac
bca
cba
cab

Time Complexity

The time complexity of the above algorithm is O(N*N!) where N is the size of the string.

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Subscribe to our weekly newsletter

Join our community of 1000+ developers and stay updated with the fast moving world of computer science

We promsie, we won't spam
Even we hate spam as much as you hate them

Books recommendation for interview preparation