String permutation iterative improvements?

Question

I have written some code (below) which iterates over each character of a string and adds that character to every index of previous permutations.

For example, in case of abc: b is added to every index of perm(a) resulting in ab, ba.

Now c is added to every index of perm(c) resulting in cab, abc, acb, cba, bac, bca.

I use a Set, to avoid duplicates.

Please review code and how it could be improved while keeping it iterative. I am particularly looking for improvements to my existing code, rather than alternative solutions(if possible), so that I can better understand the optimization process.

There may be a faster recursive solution, but I'm currently looking to improve my iterative approach.

 //method called from main
Set<String> perm(String input)
{
 Set<String> perm = new HashSet<String>();
 if(input == null || input.length() == 0 || input.length() == 1)
 {
 perm.add(input);
 return perm;
 }
 //convert to char array for iteration
 char[] arr = input.toCharArray();
 //add first char as first perm
 perm.add(String.valueOf(arr[0]));
 //iterate arr and find perm for each char
 for(int i=1; i<arr.length; i++)
 {
 perm = findPerm(String.valueOf(arr[i]), perm);
 }
 System.out.println(perm.size());
 return perm;
}
private Set<String> findPerm(String next, Set<String> perm)
{
 Set<String> perms = new HashSet<String>(perm);
 //iterate each perm to add next char at all indexes
 for(String each : perm)
 {
 perms.addAll(addAtEachIndex(each, next));
 //remove the older perms
 //for example in case of ABC, ab and ba should be deleted after making cab abc acb cba bca and bac
 perms.remove(each);
 }
 return perms;
}
private Set<String> addAtEachIndex(String each, String next)
{
 //ab c
 //^a^b^
 //0,0+c+0,1 0,1+c+1,1 0,1+c
//add the next char to each index of current perm
 Set<String> finalPerms = new HashSet<String>();
 finalPerms.add(each+next);
 finalPerms.add(next+each);
 for(int i=0; i<each.length(); i++)
 {
 finalPerms.add(each.substring(0,i+1) + next +each.substring(i+1, each.length()));
 }
 return finalPerms;
}

• Tolani: Welcome to code review . We only review workable codes and provide a variety of answers including alternative solutions. Asking about the complexity of your code is off-topic here
• Tolani: If you have multiple questions , you should try splitting the questions in different posts
• Stacky: Thanks. This is workable, I will remove the complexity question. By avoiding alternative solutions, I intended to get step by step optimization of the original solution (if possible). So that it can help understanding the process.
• Tolani: It will be nice to have some explanations on want your code does in the body of the question.

Answer 1

Descriptive naming

Set<String> perm(String input)

I would call this

Set<String> permute(String input)

When I see perm, my first thought is someone making straight hair curly. My second thought is that it might be short for permanent. Well after that I realize that in this context, you are permuting things. In my opinion, the extra three letters increases readability greatly.

 Set<String> perm = new HashSet<String>();

Ignoring the confusion with naming a variable the same as the method using it, I'd go with

 Set<String> permutations = new HashSet<>();

Now I know what's supposed to be in there.

Unless you are compiling against an old Java version, you don't need to write out String the second time. The compiler will figure it out.

Avoid casts

 char[] arr = input.toCharArray();

While this often helps when processing something character by character, I don't think it does so here.

 perm.add(String.valueOf(arr[0]));

This could be

 permutations.add(input.substr(0, 1));

So rather than converting from a String to a character array, then getting one character, then converting that character to a String, we just take a single character substr which returns the String that we want. Since a String is immutable, this can use the original backing array to hold the data. The other version would likely allocate new memory because it's not obvious that it's just taking a substring.

But even better might be

 permutations.add("");

Then we can simplify the gating test to just check for null. And we can put the rest of the logic in the loop.

 for (char current : input.toCharArray())
 {
 permutations = permute(current, permutations);
 }

Yes, I did change the name of findPerm, and I changed it to take a character rather than a String. I didn't like the name findPerm because you aren't finding anything. You are generating permutations.

If we change the first parameter to be a character rather than a String, we can use it as a character later.

The other version may be slightly more efficient, but at the cost of additional coding complexity.

And now we are processing the String character by character, so we convert it to a character array. We don't need i, as we can work with the characters directly.

Don't do unnecessary work

You have

 Set<String> perms = new HashSet<String>(perm);

and

 perms.remove(each);

But if you change the first to

 Set<String> permutations = new HashSet<String>();

Then you don't need the second line. There is no reason to put the partial permutations in the results.

Don't Repeat Yourself (DRY)

 perms.addAll(addAtEachIndex(each, next));

So addAtEachIndex creates a Set just to return it and add to another Set. Why bother?

 addAtEachIndex(each, next, permutations);

If we pass the Set into the method, we can add to it directly. So we check for duplicates once, not twice.

Choose your datatype

 finalPerms.add(each.substring(0,i+1) + next +each.substring(i+1, each.length()));

You are doing a lot of String manipulation in this section and it's not really necessary. Consider what happens if you leave next as a character rather than a String.

 StringBuilder permutation = new StringBuilder(each);
 permutation.append(next);
 permutations.add(permutation.toString());
 for (int i = each.length(); i > 0; i--)
 {
 permutation.setCharAt(i, permutation.charAt(i - 1));
 permutation.setCharAt(i - 1, next);
 permutations.add(permutation.toString());
 }

This also works with a StringBuilder rather than a String.

Now, rather than copying two substrings and a single character String into a new String, we only copy once. We do three character operations rather than five String operations. And we can keep reusing the same StringBuilder as a base.

Summary

public static Set<String> permute(String input)
{
 Set<String> permutations = new HashSet<String>();
 if (input == null)
 {
 permutations.add(input);
 return permutations;
 }
 permutations.add("");
 for (char current : input.toCharArray())
 {
 permutations = _permute(current, permutations);
 }
 return permutations;
}
private static Set<String> _permute(char next, Set<String> partials)
{
 Set<String> permutations = new HashSet<String>();
 for (String partial : partials)
 {
 addAtEachIndex(partial, next, permutations);
 }
 return permutations;
}
private static void addAtEachIndex(String partial, char next, Set<String> permutations)
{
 StringBuilder permutation = new StringBuilder(partial);
 permutation.append(next);
 permutations.add(permutation.toString());
 for (int i = partial.length(); i > 0; i--)
 {
 permutation.setCharAt(i, permutation.charAt(i - 1));
 permutation.setCharAt(i - 1, next);
 permutations.add(permutation.toString());
 }
}

I also made all the methods static as they weren't using any object state.

Time complexity

If we call the outer permute once, we call the inner _permute about \$n\$ times, where \$n\$ is the length of the input.

The first time we call the inner _permute, it calls addAtEachIndex once. The second time, once. The third time, twice. So on the \$i\$th time, we call it \$(i-1)!\$ times if there are no duplicate characters in the String. If there are duplicate characters, we call it fewer times.

The first time that we call the inner _permute, each call to addAtEachIndex iterates 0 times. The second time, one time. The third time, twice. The fourth time, six iterations. Yep, \$(i - 1)!\$ again.

Perhaps the simplest way to think about this are that there are \$n+1\$ steps to find the permutations. On the \$i\$th step, we generate \$(i-1)!\$ permutations. So for a given input length of \$n\,ドル we generate \$ \sum_{i=0}^{n} i! \$ permutations. But that's just \$\mathcal{O}(n!)\$ because it is smaller than \$ (n+1)!\$ which is \$\mathcal{O}(n!)\$.

This is as efficient as we can get asymptotically, as there are \$n!\$ results. And we must generate each one.

• Vogel612: nitpick: It's not strictly speaking the compiler that determines, which language features are available (though it defines the upper bound). It's the "language level". You can pass an argument to a java 8 compiler that will compile your code to run on a java 6 jvm. That excludes language features that were added since then, even though the compiler itself would support them. Aside from that: great answer