The basic question is this: Given a string S with possible one or more repeated characters, print all the distinct permutations of the string.
This is a question that comes up pretty often in the minds of AlgoGeeks like you guys as well as in some interviews (it came up in mine some time ago). If you're interested in a (really tight) near optimal solution - check out my blog post at http://www.divye.in/2011/06/printing-all-permutations-of-string.html - the solution given requires O(1) extra space and runs in O(n*n!) time in the worst case where there are n! different permutations available. There's a link to downloadable code too on a github archive. Suggestions welcome. -- DK PS: If you're interested in implementing algorithms for fun and practice, do check out http://github.com/swagatata/ds_and_algos - It's a work in progress but we do have implementations of some tough algorithms in C++ and Python. The repository is hosted by Swagat Konchada and I'm a contributor. Currently, we have implementations of: * Kruskals' Algorithm * Knuth Morris Pratt algorithm for Substring matching in worst case O(n + m) * Rabin Karp Algorithm for Substring matching in expected case O(n + m) * Matrix Chain Multiplication (standard Dynamic Programming) * The Josephus Problem * Standard Breadth First Search * Standard Depth First Search * Tree traversals etc. We also have some data structures which may or may not be easy to use yet. Note: All of these are work in progress, so there might be bugs etc. Please let us know if you find something that doesn't work. Feedback and contributions invited! -- DK -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
