Find all the permutations of a String in Java
I am doing some challenges on Advent of Code 2017. I highly recommend it if you’re looking for cool and short puzzles.
On one of the challenges I was looking for ways to find all the permutations of a word, also known as its anagrams. I found some interesting solutions on StackOverflow as usual, but nothing that caught my eye for elegance. Most solutions involved blind deep recursion with prefixes.
So I got sitting and thought about it, looking for an elegant, clear and concise iterative implementation. Let’s see how our brain does it: how do you sit and find the possible combinations of an ensemble? Let’s say [red, blue, green]
.

Step 1: You probably start by fetching some member. Let’s say
[blue]
. That’s your working set for now. 
Step 2: Now you get another member, for example
red
, and try the different positions to insert it in the existing set: either beforeblue
or after it. At this point you have[[red, blue], [blue, red]]
. 
Step 3: Now you get working with the set resulting from Step 2, and try inserting yet another member:
green
. You can do so either at the beginning, in the middle or at the end, and you do it for each member of the previous Step. That’s:
[[green, red, blue], [red, green, blue], [red, blue, green]]
for the first member of Step 2, 
[[green, blue, red], [blue, green, red], [blue, red, green]]
for the second.The need to call each member of the previous step calls for some collection.

And so on until we run out of members. Note that there is no Step 0 since it doesn’t matter which member we start with.
So let’s formalize, generalize and recap with pseudocode:
1 
anagrams(s) 
And this is my Java implementation:
1 
public List<String> anagrams(String s) { 
A note on runtime: each character creates 1,2,…,n additional string each time, with the addition operation taking O(1), resulting in total O(n!) runtime.
There is also no need for Sets since this efficient algorithm may produce no duplicates as long as each word only appears once. A HashSet may be used otherwise, or a TreeSet if the results need to be sorted, at the price of O(logn) operations rather than amortized constant runtime.
As for space complexity, for each length (0, n1) we allocate (n, n*(n1), …, n!) members. This ends up with O(n!) complexity.
As for the runtime, because we expect a result of size O(n!), the complexity cannot be reduced, but the actual allocated space can, by reusing the existing collection throughout, instead of throwing the previous level’s collection.
And of course, this algorithm works just as well to iterate over the combinations of any kind of collection.