loading...
Nlogn

Print all permutations of a string with unique characters

mayankjoshi profile image mayank joshi Originally published at nlogn.in ・2 min read

interview-question (4 Part Series)

1) Find if a path is possible in a NxM for reaching bottom right form top left 2) Find all possible subset of a given set 3) Print all permutations of a string with unique characters 4) DP - Coin Change: Find the number of ways of representing n cents

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 the 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

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.


This post was originally published at nlogn

interview-question (4 Part Series)

1) Find if a path is possible in a NxM for reaching bottom right form top left 2) Find all possible subset of a given set 3) Print all permutations of a string with unique characters 4) DP - Coin Change: Find the number of ways of representing n cents

Posted on Mar 25 by:

mayankjoshi profile

mayank joshi

@mayankjoshi

I love system design and most of the time I find myself learning or designing one of them. I'm highly active on twitter, So ping me there.

Nlogn

nlogn is a Computer Science portal specially designed to help you prepare for product-based companies interviews by practicing a wide variety of problem-related to system Desing, Data-Structure and much more.

Discussion

markdown guide