Performance: JAVA permutation

Question

So, I had this code to generate permutations of a word, and store it to a HashSet for later comparing with a dictionary. But when the input word has 10 or more letters, the permutation process becomes ridiculously slow. Besides using permutation algorithm, is there any ways to improve the performance of this process?

/**
 * Returns a HashSet of the string permutation.
 *
 * @param prefix an empty string.
 * @param str the string to create perm.
 * @return permutations a HashSet of the permutation.
 */
private static HashSet<String> permutation(String prefix, String str) {
    HashSet<String> permutations = new HashSet<String>();
    int n = str.length();
    if (n == 0) {
        permutations.add(prefix);
    } else {
        for (int i = 0; i < n; i++) {
            permutations.addAll(permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n)));
        }
    }
    return permutations;
}

Specify an initial capacity that matches the expected number of entries in your `HashSet`, so that it doesn't have to expand all the time. — Henrik Aasted Sørensen, Feb 07 '17 at 08:43
Complexity of your algorithm is O(n!). this is a worst complexity which could be. for 10 it takes 3628800 steps — Vlad Bochenin, Feb 07 '17 at 08:49
@Henrik well, the thing is I don't know the expected number, it could be 1000000 or 100000000 depending on the input string's length. I'm not sure though if using HashSet is the best option. — Tiancheng Xu, Feb 07 '17 at 08:49
@TianchengXu: Well, surely it's possible to calculate based on the string's length. Anyway, just an approximation may cut down on runtime. Resizing a map to accomodate more entries than expected can be quite expensive if it contains a lot of entries. — Henrik Aasted Sørensen, Feb 07 '17 at 08:52
@VladBochenin, it meant to generate every single combination of the input string and check which is an English word later. So...I guess the best way to do is to use some sort of algorithm to eliminate the useless combinations. — Tiancheng Xu, Feb 07 '17 at 08:52
@TianchengXu: You should consider normalizing the string first (e.g. by sorting its letters alphabetically) and then use that as a key in the map instead. Generating all combinations seem like an infeasible approach. — Henrik Aasted Sørensen, Feb 07 '17 at 08:53
@TianchengXu: Perhaps take a look at this question: http://stackoverflow.com/q/12477339/13075 . I think it's in the area of what you're trying to do. — Henrik Aasted Sørensen, Feb 07 '17 at 08:55
@TianchengXu take a look into this algorithm for example http://www.journaldev.com/526/java-program-to-find-all-permutations-of-a-string — Vlad Bochenin, Feb 07 '17 at 08:56

score 2 · Answer 1 · edited May 23 '17 at 12:01

The short answer: There is no better Complexity than O(n!) for permutation

O(n!) is the worst time-complexity I can imagine. You can't find a more efficient way to handle permutations. For further information see:

Stackoverflow-Wiki

Big-O

The long answer:

You can improve your code (not your algorithm) by using Javas StringBuffer-Class to get faster results.

public static HashSet<StringBuffer> permutationNew(StringBuffer sb_prefix, StringBuffer sb_str) {
    HashSet<StringBuffer> permutations = new HashSet<>();
    int n = sb_str.length();
    if (n == 0) {
        permutations.add(sb_prefix);
    } else {
        for (int i = 0; i < n; i++) {
            permutations.addAll(permutationNew(sb_prefix.append(sb_str.charAt(i)), new StringBuffer(sb_str.substring(0, i)).append(sb_str.substring(i + 1, n))));
        }
    }
    return permutations;
}

I tested this code and compared it with your old method. Here are my results.

 ____________________________________
| inputlength | oldmethod | newmethod|
 ------------------------------------
| 1           | 0 ms      | 0 ms     |
| 2           | 0 ms      | 0 ms     |
| 3           | 1 ms      | 0 ms     |
| 4           | 1 ms      | 0 ms     |
| 5           | 2 ms      | 0 ms     |
| 6           | 9 ms      | 3 ms     |
| 7           | 71 ms     | 38 ms    |
| 8           | 400 ms    | 66 ms    |
| 9           | 1404 ms   | 377 ms   |
| 10          | 9696 ms   | 2095 ms  |
L_[...]__________[...]______[...]____J

If there are to many methods referencing your permutation-method, create a wrapper around the optimized method:

private static HashSet<String> permutation(String prefix, String str) {
    HashSet<StringBuffer> permutations = permutationNew(new StringBuffer(prefix), new StringBuffer(str);
    //create new HashSet<String> using permutations-HashSet and return it...

Performance: JAVA permutation

1 Answers1