Printing all permutations of a string is a very common interview question. We'll discuss this problem and some interesting variations of it. The original problem of string permutation says, "

*print all permutations of a string*". As an example, if the string is "abc" there are 6 permutations {abc, acb, bac, bca, cab, cba}. Assume that string contains no duplicate elements.

Solution: show
There are many ways in which this problem can be solved. The most easiest of the ways is to code it using simple yet powerful recursion technique.

function permute(str, d)
if d == length(str)
print str
else
for i <- d to length(str)
swap(str[d] <-> str[i]) // swap character for permutation
permute(str, d + 1)
swap(str[d] <-> str[i]) // undo swap for parent call

Above code performs the swapping operation twice. First time to generate all possible permutations of character at that level and second time to restore to the original string. It is important to restore to the original string (as passed to this call), otherwise the algorithm ends up printing redundant permutations. Additionally, this code assumes that there are no duplicates in the string, else it fails.

There are other ways in which string permutation can be printed that require circular shifting, but it cant get any simpler than above.

*Source Code*:

permute_unique_chars.py
Lets us assume that string can contain duplicates. How do we print all non-redundant permutations of the string. For ex. If string is "abab" the permutations are {baab, abba, abab, baba, bbaa, aabb}

Solution: show
Clearly the solution to first problem fails here. This is due to fact that we generate all permutations of the string after the swapping step. Same character could get swapped to dth spot again, leading to redundant permutations. A very simple trick solves the game. The trick is to

pre-sort the string on alphabetical order. Now we need to ensure that while we are swapping, to generate permutation for that particular character, if that matches the last swapped character we ignore generating permutations. Effectively, we are doing a cyclic shift and before the end of the call we reset the cyclic shift. The following code implements the same:

function permute(str, d)
if d == length(str)
print str
else
lastSwap = Nil
for i <- d to length(str)
if lastSwap == str[i]
continue
else
lastSwap = str[i]
swap(str[d] <-> str[i]) // swap character for permutation
permute(str, d + 1)
for i <- d to length(str)-1
str[i] = str[i+1]
str[length(str)] = last

If the string is pre-sorted alphabetically then the above algorithm works magically. Note that in this case, after permute is called, we do not undo the swap. This ensures that we are cyclic shifting and hence the intermediate str from d to l is also sorted. After the for loop call, we reverse the cyclic shift. The reason is that sorting ensures that if there are duplicates then the second occurrence of the duplicate element is picked immediately after we finish generating permutations for the first occurrence of the duplicate element. If sorting is not allowed, then you need to maintain a local hashtable (local to each function call), that maintains characters swapped to dth spot and ensures that duplicate candidates are discarded. Presort and make life simple.

*Source Code*:

permute_chars.py
Some other constraints could be added to make the problem more interesting. One such constrain could be of partial ordering of characters. For Ex. 'a' should appear before 'c', and 'b' should appear before 'c' in all permutations. There can exist ordering that leads to no permutation of the string such as 'a' precedes 'b', 'b' precedes 'c', 'c' precedes 'a'. Additionally implementing the permutation algorithm in these cases require checking for ordering violation at each permutation level or just at the leaf of recursion, depending on whether checking for ordering violations is more costly or generating all permutations.

An interesting problem, that talks of special kind of ordering and can be very efficiently computed is as follows: Assume that the string is made up of equal number of '{' and '}'. You need to print all permutations of this string which could satisfy a C compiler i.e. an ending bracket is balanced by an opening bracket. For ex. for '{{}}' the permutations are [{{}}, {}{}].

Solution: show
The hard question is how many such permutations exist. For N open and N close brackets, the number of such permutations is Nth Catalan number = 1/(n+1) * factorial(2*N)/factorial(N)^2. The solution is derived from the problem:

Number of paths in rectangular grid.

Permutation problems can be easily solved using recursion. The trick is to formulate all the possible cases at a particular level and code according to the formulation. The steps used below illustrate this approach. Let's formulate the problem in general sense. Assume that at a given step of recursion, we have n open brackets and m closed brackets that are not used so far. Now we can formuate each and every case for a given (n,m) and code the possible substeps.

Problem Formulation:
(n,m) ---> NOT POSSIBLE, if m < n
(n,m) ---> PRINT AND DONE, if m = 0 and n = 0
(n,m) ---> (n-1, m) if n > 0
+
(n, m-1) if m > 0 and m > n

The above formulation is generic and takes into account all possible input values of (n,m). If we put following constraint on the initial value of n and m such as following, then actual implementation can omit some of the above cases:

Constraints:
n > 0
m == n

The actual implementation that follows above constraints and problem formuation:

function permute(str, n, m)
if m == 0
print str
else
if n > 0
permute (str + '{', n - 1, m);
if m > n
permute (str + '}', n, m - 1);

To enforce the above mentioned constraints, permute function should be kept as inner/private function and the actual function that should be exposed is as follows:

function GenerateCStyleBrackets(N)
if N <= 0
return
str = new String[2 * N]
permute(str, N, N) // str is passed as pointer.

The memory cost is O(N). The maximum stack depth is also O(N). So total space cost is O(N).

*Source Code*:

permute_brackets.py
I found this site using [url=http://google.com]google.com[/url] And i want to thank you for your work. You have done really very good site. Great work, great site! Thank you!

ReplyDeleteSorry for offtopic

P(ABCD)={A.P(BCD) , B.P(CDA) ,C.P(DAB) ,D.P(ABC)}

ReplyDeleteThis is what happening in the above code.I think,this will help u guys.

It is useful to try everything in practise anyway and I like that here it's always possible to find something new. :)

ReplyDeletei do not understand the logic of asking these questions in an interview. either you know the answer or you dont. do they want to know how much you have prepared for the interview or your potential

ReplyDeletehttp://layerinside.blogspot.com/2011/02/permutation-of-string.html

ReplyDeletefor the case of string with duplicate characters, i think u need to sort the string local to each function call....sort the string from d till length(str)...

ReplyDeleteGreat post!

ReplyDeleteNice solution here as well:

http://www.programmerinterview.com/index.php/recursion/permutations-of-a-string/

nice trick is used here, in case of repetition. otherwise the bruteforce comparison of all possible permutations to find distinct permutations increases the complexity very much.

ReplyDeletethanx for the code, it was very useful.

Hi,

ReplyDeleteI guess the permutation for repeated characters wont work for the input "aacb".

Please correct me if i'm wrong.

In solution 1, actually, the second swap may not be necessary.

ReplyDeleteWill it work this input "aabc" ?

ReplyDeleteIt is sorted. But I don't think it will work.

Please correct me if I am wrong.

ReplyDeleteThanks for the post.-- Mosa

The sorting trick for dup character is not correct.

ReplyDeleteAnantha : The algorithm works for aacb input.

ReplyDeleteThanks

Algorithm for repeated input is now modified slightly to be more efficient and ensures that sub strings (between d to length(str)) are always sorted if they are pre-sorted.

ReplyDeletesorry i dont understand te initial value that should be assignd to d if some knw help me

ReplyDeleteom: thanks for the visualization. Very nice to see that.

ReplyDeleteWhat I'm racking my brains about now is say you have a set S{0,1,2,3,4,5,6,7,8,9} and you want a subset s{x} elements, say x = 5. What are all possible permutations s{...} of length x using all elements in S?

Great work, thanks.. It helped a lot for my homework

ReplyDelete