January 23, 2009

String Permutations

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

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

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

Source Code: permute_brackets.py

17 comments:

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

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

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

    ReplyDelete
  3. i 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

    ReplyDelete
  4. http://layerinside.blogspot.com/2011/02/permutation-of-string.html

    ReplyDelete
  5. for 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)...

    ReplyDelete
  6. Great post!

    Nice solution here as well:

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

    ReplyDelete
  7. 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.

    thanx for the code, it was very useful.

    ReplyDelete
  8. Hi,

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

    Please correct me if i'm wrong.

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

    ReplyDelete
  10. Will it work this input "aabc" ?
    It is sorted. But I don't think it will work.

    Please correct me if I am wrong.

    ReplyDelete
  11. Thanks for the post.
    -- Mosa

    ReplyDelete
  12. The sorting trick for dup character is not correct.

    ReplyDelete
  13. Anantha : The algorithm works for aacb input.

    Thanks

    ReplyDelete
  14. 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.

    ReplyDelete
  15. sorry i dont understand te initial value that should be assignd to d if some knw help me

    ReplyDelete
  16. om: thanks for the visualization. Very nice to see that.

    What 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?

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

    ReplyDelete