Find all Lexicographic Permutations of a String

In this post, we will see how to find all lexicographic permutations of a string where repetition of characters is allowed.

 

For example, consider string ABC. It has following lexicographic permutations with repetition of characters –


AAA AAB AAC ABA ABB ABC ACA ACB ACC BAA BAB BAC BBA BBB
BBC BCA BCB BCC CAA CAB CAC CBA CBB CBC CCA CCB CCC

 


 

We can use recursion to solve this problem. We start by sorting the string so that the characters are considered in lexicographical order. Then at any point in the recursion, the current index in the output string is filled with each character of the input string one by one and we recuse for the next index.

C++

Download   Run Code

Output:

AAA AAB AAC ABA ABB ABC ACA ACB ACC BAA BAB BAC BBA BBB
BBC BCA BCB BCC CAA CAB CAC CBA CBB CBC CCA CCB CCC

Above solution doesn’t handle duplicates in the output. For example, for string AAB it prints –


AAA AAA AAB AAA AAA AAB ABA ABA ABB AAA AAA AAB AAA AAA
AAB ABA ABA ABB BAA BAA BAB BAA BAA BAB BBA BBA BBB

Here, AAA is repeated 8 times, AAB, ABA, BAA is repeated 4 times and ABB, BAB, BBA is repeated 2 times. Below code efficiently handles duplicates in the output –

C++

Download   Run Code

Output:

AAA AAB ABA ABB BAA BAB BBA BBB

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
Sort by:   newest | oldest | most voted
Marius
Guest
Marius

is that better than std::next_permutation ?

wpDiscuz