Permutation of a string eliminating duplicates

Question

This code lists the permutations of the string, and eliminates duplicates if any. I'm looking for code review, best practices, optimizations etc.

I'm also verifying complexity: \$O(n! * n)\$ as time complexity and \$O(n * n)\$ as space complexity, where \$n\$ is length of the input string.

public final class Permutation {
 private Permutation() {
 };
 /**
 * Return permutation of a given string.
 * But, if the string contains duplicate characters, it 
 * takes care to eradicate duplicate permutations.
 * 
 * @param string the string whose permutation needs to be found out.
 * @return a list with permuted values.
 */
 public static List<String> permutation(String string) {
 final List<String> stringPermutations = new ArrayList<String>();
 permute(string, 0, stringPermutations);
 return stringPermutations;
 }
 private static void permute(String s, int currIndex, List<String> stringPermutations) {
 if (currIndex == s.length() - 1) {
 stringPermutations.add(s);
 return;
 }
 // prints the string without permuting characters from currIndex onwards.
 permute(s, currIndex + 1, stringPermutations);
 // prints the strings on permuting the characters from currIndex onwards.
 for (int i = currIndex + 1; i < s.length(); i++) {
 if (s.charAt(currIndex) == s.charAt(i)) continue;
 s = swap(s, currIndex, i);
 permute(s, currIndex + 1, stringPermutations);
 }
 }
 private static String swap(String s, int i, int j) {
 char[] ch = s.toCharArray();
 char tmp = ch[i];
 ch[i] = ch[j];
 ch[j] = tmp;
 return new String(ch);
 }
 public static void main(String[] args) {
 for (String str : permutation("abc")) {
 System.out.println(str);
 }
 System.out.println("------------");
 for (String str : permutation("aabb")) {
 System.out.println(str);
 }
 }
}

• abuzittin gillifirca: Your space complexity is definitely not O(nn). And cannot be less than O(nn!) (for n distinct chars) because you have n! different arrays with n chars each. This program fills 2GB heap and hits OutOfMemoryError in few minutes if not seconds. Just try it with about a dozen different characters.
• Jayesh: different approach: javabypatel.blogspot.in/2015/08/…

Answer 1

1. Best beginner's code I've seen. Possibly ever. Admittedly, I haven't reviewed too many beginner's programmes, but this one was definitely an easy review.
2. Only style change I'd suggest is to avoid the single-line if (s.charAt(currIndex) == s.charAt(i)) continue;. It's totally valid, but easy to miss. At least put the continue on a new line; many people prefer to put it in braces, too.
3. Since your main() method is obviously a way to test the rest of the code, I'd suggest pulling the loops that are currently in there into a self-documenting method like testPermutation(String arg) and call that from main().
4. Now that your main method is so simple (it just contains testPermutation("abc"); and testPermutation("aabb");), change it to either
   1. loop over the arguments to main(), so you can call your program like java yourpackage.Permutation abc aabb, or
   2. read strings from stdin until user exits.
5. To measure time complexity, you can maintain a counter that gets incremented inside swap(), and infer from that result. I think you'll find that it's much less than n! * n.
6. Space complexity is the same as time complexity, since you create a new String every time you swap. Or depending on how you define "space complexity", I suppose it might be n * time complexity, since each time you swap, you create a String of length n.

Answer 2

It does not eliminate the duplicates. In permute method you check only two consecutive char elements. If you change the ordering of duplicate elements in your second input for the test such as "abab" then it will print duplicate permutations.

• janos: Very well spotted, nice answer, welcome to Code Review!

Answer 3

• When you have potentially very large number of return values. You can return return an Iterable<T> which lazily generates the results one by one. That way you will not keep GC from collecting the values you no longer need. For example you do not need a particular permutation of the string after you printed it. You can use guava library which has useful utilities to work with Iterables and Iterators for this.

• Do not make you class final or disable the default constructor. It allows you nothing and makes the work of people that may have to use it in the future harder, by making your code hard or impossible to use with byte-code manipulation and reflection where most testing, ORM, DI, AOP tooling depend on. This is particularly useless with classes that have no virtual methods or any fields, no one would want to extend them anyway, let alone accidentally.