2
\$\begingroup\$

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;
    }

}
\$\endgroup\$
  • \$\begingroup\$ "How can I improve management of my strings?" StringBuilder addresses this as well as the performance problem. \$\endgroup\$ – Timothy Truckle Oct 27 '16 at 16:26
  • 2
    \$\begingroup\$ "The only advantage I can think of is clarity but this code seems too small for that to matter much." readability is the second most important property of code (right after correctness), so no method is "too small" to be improved for readability! \$\endgroup\$ – Timothy Truckle Oct 27 '16 at 16:29
  • \$\begingroup\$ String concatenation uses StringBuilder under the covers whenever you append two String objects using a + operator. If you are only appending two String objects on each pass, the use of StringBuilder will just make your code harder to read for no net gain. \$\endgroup\$ – Rick Ryker Apr 19 '17 at 15:36
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.