Iterative solution for generating all permutations of a string

Question

I know the runtime for generating all permutations is supposed to be \$O(n!)\$. I'm not sure if the code I wrote for it runs in \$O(n!)\$ though. I'm having trouble analyzing its runtime.

The for(char c: cArray) part is in \$O(n)\$. What about for (String s: currResults) and for (int i = 0; i < s.length() + 1; i++)?

public static Set<String> getPermutations(String str) {
        char[] cArray = str.toCharArray();
        Set<String> realRes = new HashSet<String>();
        Set<String> results = new HashSet<String>();
        for (char c : cArray) {
            Set<String> currResults = new HashSet<String>(results);
            String charToAdd = String.valueOf(c);
            results.add(charToAdd);
            for (String s : currResults) {
                for (int i = 0; i < s.length() + 1; i++) {
                    String newWord = s.substring(0, i) + charToAdd + s.substring(i);
                    if (newWord.length() == str.length()) {
                        realRes.add(newWord);
                    }
                    else {
                        results.add(newWord);
                    }
                }
            }
        }
        return realRes;
    }

Answer 1

Time complexity analysis

Let's think about what this does.

        for (char c : cArray) {

This says that for each character in the string (since cArray is the character array view of the string), we iterate once. As you note, this is \$O(n)\$ where \$n\$ is the number of characters in the string.

        Set<String> currResults = new HashSet<String>(results);

This is \$O(m)\$ where \$m\$ is the number of entries in the Set. Note that that will change as you go.

        String charToAdd = String.valueOf(c);
        results.add(charToAdd);

This takes constant time.

        for (String s : currResults) {

This takes \$O(m)\$ time again.

            for (int i = 0; i < s.length() + 1; i++) {

This takes \$O(l)\$ time, where \$l\$ is the length of this string. Again, this will change over time.

                String newWord = s.substring(0, i) + charToAdd + s.substring(i);

This takes \$O(l)\$ time, as it involves copying s to a new string.

                if (newWord.length() == str.length()) {
                    realRes.add(newWord);
                }
                else {
                    results.add(newWord);
                }

This takes constant time.

We do \$n\$ iterations of the outer loop.

First iteration

\$n\$ is the number of characters in str and will be throughout.

\$m\$ is 0. We haven't put any entries in the set yet.

\$l\$ doesn't exist. We never get to that section of code.

We end with one entry in results and no entries in realRes.

Second iteration

\$m\$ is 1.

\$l\$ is 1.

We end with three entries in results and no entries in realRes.

Third iteration

\$m\$ is 3. This is 2 + 1.

\$l\$ ranges from 2 to 1.

We end with nine entries in results and no entries in realRes.

Fourth iteration

\$m\$ is 9. This is 3 * 2 + 2 + 1.

\$l\$ ranges from 3 to 1.

We end with forty entries in results and no entries in realRes.

nth iteration

We end with \$n!\$ entries in realRes. We add increasing numbers of strings to results, equal to \$\sum\limits_{i=1}^{n-1} i!\$. Note that that is less than \$n!\$.

Note that this assumes that all the characters in the string are different. If some characters repeat, this will exaggerate the number of entries. Of course, for Big-O notation, that's fine. So we can say that overall this is still \$O(n!)\$.

Alternately styled code

    public static Set<String> getPermutations(String str) {
        Set<String> results = new HashSet<>();
        Set<String> partials = new HashSet<>();
        for (char c : str.toCharArray()) {
            List<String> current = new ArrayList<>();
            String charToAdd = String.valueOf(c);
            for (String s : partials) {
                for (int i = 0; i <= s.length(); i++) {
                    String newWord = s.substring(0, i) + charToAdd + s.substring(i);
                    if (newWord.length() == str.length()) {
                        results.add(newWord);
                    } else {
                        current.add(newWord);
                    }
                }
            }

            partials.add(charToAdd);
            partials.addAll(current);
        }

        return results;
    }

I don't like the name results for what you had. It's not results. It's partial permuations. So I changed it to partials.

With the name results available, I'd prefer that to realRes.

I find it easier to read if we do the toCharArray in the for loop itself. That way I don't have to look around to find what cArray is.

Rather than copy the entire set to another set on every iteration, I'd rather just copy the things that I'm adding. So I made a List for that purpose. That (and moving the charToAdd add) allows us to loop directly over partials rather than the new collection.

We can save a math operation if we say i <= s.length() rather than i < s.length() + 1. I also find it a bit clearer about what it is doing.

The Java standard is to do the fully cuddled else. It's not a big deal if you do it the other way, but I changed that on my way through.