The task of listing every permutation of a string is trivial when the string contains only two characters. Using this knowledge, the same problem can be solved for a string of three characters relatively easily. Accordingly, the permutations of a string of length n are easy to list if we know the permutations of a substring of length n-1.
This property is easy to see, if not obvious within a few minutes of thinking about this problem. Since the problem can be simply defined recursively, it can also be solved recursively with relative ease. In this solution, I use Clojure to demonstrate that recursion lends itself nicely to functional programming.
This is a perfect problem for using example input and working through the solution intuitively, by hand before writing down an algorithm. The simplest case (other than the trivial single character string case), a two character string gives us the original string and another string with the characters swapped:
"he" => "he", "eh"
Taking the concept one step further, with a three character string requires breaking down the problem into subproblems. Each subproblem also requires us to list the permutations of each substring -- thus, recursion. Looking at an example worked out by hand:
"her" => "her", "hre", "ehr", "erh", "rhe", "reh"
We can see a pattern appear. I like to view this pattern as the following:
- The last two characters of the string are swapped, giving the first permutation (other than the original string).
- The first character of the string is 'threaded' through each position of both the new permutation and the original string:
"her" => "h" + "_e_r_"
Where the _ represent positions that the first character can take. This character can only be viewed as a string. I like to think
about this string as our 'thread' which makes its way through each position of the other string (the _s).
This concept can be extrapolated to longer strings by treating the first section of string as the thread which is placed in each position in the permutations of the substring (in the above example this is "er").
When thinking about this problem I imagine a generic string which is halfway through the permutation process. The last few characters
have already been permuted in every position amongst that substring and are represented by the wildcard *, while the first substring
contains the actual letters of the string. The * wildcard characters are surrounded by _ placeholders for the threading string.
"bats" => "ba" "_ * _* _"
Where "ba" will go into every _ position and * represents either 't' or 's'.
I also like to think of this problem as a problem similar to calculating the number of permutations of objects in a line. For example, given 4 objects, we can imagine that there are four positions:
_ _ _ _
Each position can be filled by a single object, once an object is in a position, it cannot be placed in another position. There is the choice of 4 objections for the first poisition ad thus only 3 for the second once an object has been placed in the first position, and so on. Thus, the number of permutations is given by:
4 * 3 * 2 * 1
This helps me in thinking about this problem since characters in a string can be though of as the objects described above, and the product of any two digits occupying the above positions gives the number of permutations of those characters.
Before we write the function which lists all permutations of a string, we need to include clojure.string/join which joins an
arbitrary number of strings or character literals.
(use '[clojure.string :only (join)])Additionally, we define a helper function which takes a string and a thread and returns a list of strings with the thread at each position in the string. This simplifies the recursive function defined next.
(defn ins-str [string substring index]
(join (list (subs string 0 index) substring (subs string (inc index)))))
(defn thread-str [string thread-str]
(map (fn [index]
(ins-str string thread-str index))
(range (inc (count string)))))The following recursive function can still be inproved. Any thoughts? Is it possible to move the recursive call to a tail call to take
advantage of Clojure's tail call optimziation with recur?
(defn perms-of
([in-str]
(if (= 2 (count in-str))
(list in-str (join (reverse in-str)))
(perms-of (first in-str) (join (rest in-str)))))
([thread to-permute]
(flatten (map #(thread-str % thread) (perms-of to-permute)))))That's it. I've seen some much more complicated and difficult-to-wrap-your-head-around solutions which involve an iterative approach. The recursive solution is neat and straighforward. Additionally, other solutions I've seen require filtering out repeats whereas this one doesn't. This is simpler to achieve using the functional style which acheives results by performing transformations rather than changeing state.