Most effective way to find permutation in Java [with a lower asymptotic complexity]

Question

My objective is to find all the permutations of a String. And after some quick search, I found a neat way to find all the permutations of the String. ie

    private static void permutation(String prefix, String str) 
    {
        int n = str.length();
        if (n == 0)
            System.out.println(prefix);
        else 
        {
            for (int i = 0; i < n; i++)
                permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
        }
   }

and I believe the complexity of this method is O(n!) (correct me if I am wrong). And my question is: Can I tweak this anymore to improve the efficiency of this? Or is there a better alternative to generate all the permutations?

Possible duplicate of [Faster string permutation](http://stackoverflow.com/questions/10962682/faster-string-permutation) — Whymarrh, Mar 07 '16 at 18:13
@dr_debug what do you mean by removing recursion for performace purposes? Are you suggesting to go with loops instead of recursion? — OBX, Mar 07 '16 at 18:18

score 0 · Answer 1 · edited May 23 '17 at 11:52

It looks like you're using this answer:

Generating all permutations of a given string

The comments on that question are quite informative. You have a number of inefficiencies around String manipulations, it prints duplicates, it doesn't account for repeated characters, and a few others are noted.

I would look through those, implement the suggested changes and then compare to see what your run-time improvements are. Fundamentally I believe you are bounded by n! and the most you can do is memory/data structure tweaks to avoid space/time complexity explosions due to inefficient application of the structures used here.

Most effective way to find permutation in Java [with a lower asymptotic complexity]

1 Answers1