Iterative Approach to Find Permutations of a String in C++ and Java

In this post, we will discuss how to find permutations of a string using iteration.


 

In the previous post, we have seen recursive implementations to find permutations of a string using backtracking and STL. In this post, we will cover iterative implementation for the same.

Also recursive implementation doesn’t handle strings containing duplicate characters and will print duplicate permutations. For example, for string ABA, permutations ABB, ABA and AAB will be printed two times. The first iterative implementation discussed below using next_permutation can handle strings with duplicate characters and don’t repeat the permutations.

 

1. Using std::prev_permutation or std::next_permutation

The idea is to sort the string and repeatedly calls std::next_permutation to generate the next greater lexicographic permutation of a string, in order to print all permutations of the string. We can also sort the string in reverse order and repeatedly calls std::prev_permutation to generate the previous lexicographic permutation of a string.

Below iterative implementation avoids using std::next_permutation and implements our own next_permutation. Below in-place algorithm generates the next permutation lexicographically.

  1. Find largest index i such that str[i-1] is less than str[i].
     
  2. We’re already at highest possible permutation if i happens to be the first index of the string, and we return false. 
     
  3. If i is not the first index of the string, then the substring str[i..n-1] is sorted in reverse order i.e. str[i-1] < str[i] >= str[i+1] >= str[i+2] >= ... >= str[n-1].
     
  4. Find a highest index j to the right of index i such that str[j] is greater than str[i–1] and swap characters at index i-1 with index j.
     
  5. Reverse the substring str[i..n-1] and return true

C++

Download   Run Code

Output:

ABC ACB BAC BCA CAB CBA

Java

Download   Run Code

Output:

ABC ACB BAC BCA CAB CBA

 

2. Using controller array

Please refer this link for details on below algorithm.

C++

Download   Run Code

Output:

ABC BAC CAB ACB BCA CBA

Java


 

Download   Run Code

Output:

ABC BAC CAB ACB BCA CBA

 

3. Using STL/Collections

Below implementation uses list to store the partially constructed permutations and then use those partial permutations to construct the final permutations in later iterations.

C++

Download   Run Code

Output:

CBA BCA BAC CAB ACB ABC

Java

Download   Run Code

Output:

[CAB, ACB, ABC, CBA, BCA, BAC]

The time complexity of above solutions remains same as recursive implementation i.e. O(N!) where N is the length of the string.

 
References:

1. Stack Overflow

2. Permutation Algorithms Using Iteration and the Base-N-Odometer Model (Without Recursion)

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz