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
– Henrik Aasted Sørensen, Commented Feb 7, 2017 at 8:43
Complexity of your algorithm is O(n!). this is a worst complexity which could be. for 10 it takes 3628800 steps — Vlad Bochenin
– Vlad Bochenin, Commented Feb 7, 2017 at 8: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
– Tiancheng Xu, Commented Feb 7, 2017 at 8: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
– Henrik Aasted Sørensen, Commented Feb 7, 2017 at 8: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
– Tiancheng Xu, Commented Feb 7, 2017 at 8:52

Community · Accepted Answer · 2017-05-23 12:01:34Z

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...

Collectives™ on Stack Overflow

Performance: JAVA permutation

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related