Generating all unique permutations of a string

Question

Here is a plan for generating the permutations of S: For each item x in S, recursively generate the sequence of permutations of S - x, and adjoin x to the front of each one. This yields, for each x in S, the sequence of permutations of S that begin with x. Combining these sequences for all x gives all the permutations of S:

The plan to generate all the permutations of a set S

I would like to use the process described above to generate the permutations of a string.

• I used LinkedHashSet because I'd like to get rid of all the duplicate permutations if there are the same characters in the string. Besides, the add operation is constant.
• I will have to remove a character from a string lots of times. But Syntactically, since this is recursive, I will only do the removing of characters once in the code definition (str.substring(0, i)+str.substring(i+1)). Do I still need to put this code to another method? The only advantage I can think of is clarity but this code seems too small for that to matter much.
• I don't know much about how to analyze my code, but since we need to find the ways to order the set while removing every character and putting this character in front of each one, I think the running time is n factorial+n. For example, if we have a string with 3 characters, we would find the ways of ordering 3 subsets (the subsets where the first, second and third characters are removed). Each of those subsets results in two ways, that's why we get 3*2 ways after putting the removed character in the front of each. The +n part is the substring operations which is O(n). Is this all correct?
• Regardless of if my code runs at n factorial or not, I think this is absolutely, horribly, extremely slow. How can I make it faster?
• I found that java string's immutability is helpful to what my code is doing. But I still feel that I am wasting a lot of string objects because most of them will be trashed anyway when I append a character to it. How can I improve management of my strings??

Please review my code.

public class Permutation {

    public Set<String> permute(String str) {
        Set<String> res = new LinkedHashSet<>();
        if (str.isEmpty()) {
            res.add(str);
        } else {
            for (int i = 0; i < str.length(); i++) {
                for (String s : permute(str.substring(0, i)+str.substring(i+1))) {
                    res.add(str.charAt(i)+s);
                }
            }
        }
        return res;
    }

}

Answer 1

Pay attention to your substrings. Given s = "abc", then the following return empty strings.

String pre = s.substring(0,0);
String post = s.substring(3);

Consider (temporarily) adding logging statements inside your innermost loop and examining the results of calling permute("abc") to see how many times you add the same strings to the set. Try to avoid adding to the set a value already in the set concatenated to an empty string, since this gives you no new values in the set.