String permutations

Question

So I have tried the famous string permutation algorithm. Example for those who are not familiar with the algorithm: ABC -> ABC, ACB, BAC, BCA, CBA, CAB

public static HashSet<String> stringPermutation(String s) {
    HashSet<String> perms = new HashSet<String>();
    stringPermutation(s.toCharArray(), perms, 0);
    return perms;
}

private static void stringPermutation(char[] strArray, HashSet<String> bucket, int index) {
    if(index == strArray.length) {
        return;
    }
    //saves the 'state' of strArray
    char[] tmp = new char[strArray.length];
    for(int i = 0; i < strArray.length; i++) {
        tmp[i] = strArray[i];
    }
    //iterate over strArray
    for(int i = index; i < strArray.length; i++) {

        for(int j = 0; j < strArray.length; j++) {
            strArray[j] = tmp[j];
        }
        swapChars(strArray, i, index);
        bucket.add(new String(strArray));
        stringPermutation(strArray, bucket, index+1);
    }
}

private static void swapChars(char[] array, int a, int b) {
    //check if indexes are out of bounds
    if((a >= 0 && a < array.length) && (b >= 0 && b < array.length)) {
        char temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

What bothers me the most is the fact that for every function call the char array representing the string is deep copied to a temporary array. If I don't do that the permutations effect each other and the result is wrong.

Answer 1

Basic review

Dealing with the simple things first, (code style and best practices):

• you should expose interface types instead of concrete types whenever you can. Your method should not return a HashSet<String>, but a Set<String>. I would actually reduce it further to a Collection, and because I wanted to maintain the order-of-insertion for some debugging, I used a LinkedList in my code.

• Similarly, you should omit the generic type when the compiler can infer it. This is normally on the right-hand side of an assignment. So, this code:

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

  should be:

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

  (note the change to Set on the left as well).

• when copying data from one array to another, use the System.arraycopy or Arrays.copy(...) functions. This code:

  char[] tmp = new char[strArray.length];
  for(int i = 0; i < strArray.length; i++) {
      tmp[i] = strArray[i];
  }
  

  should be:

  char[] tmp = Arrays.copyOf(strArray, strArray.lenght);
  

  (although, I agree that the copy should not be needed).

• When doing the swap, it concerns me that you have put in the guard clause for ensuring the values are in-bounds. When you have control over the input values in the same code/file, you should ensure that out-of-bounds conditions don't happen, and save yourself the cost of the check (although, when you have "library" code where you don't control the inputs, then you need to validate them!).

• some of your comments are redundant... do you really need: //iterate over strArray for the code for(int i = index; i < strArray.length; i++)? In fairness, the comment, if there, should make special reference to the non-zero starting point of the iteration, you're only iterating the tail of the array, so the comment is a bit misleading!

Right, that's the basics. The positives are that:

• your variable names are good, and meaningful
• your style is consistent (indentation, spacing, etc.) (I am not a fan of no-spaces-after for, if, and other flow statements.... but consistency trumps personal preferences).
• the comments are mostly good, and useful.

The clone

Now, about the array clone... you don't need it. Your issue is that you should unswap things after swapping them:

• do a swap
• process the remaining data with the given swap
• undo the swap to restore the state.

This relies on each step having a deterministic restoration, and the array being reverted after each attempt. A bug in the code will screw up that symmetry, so you have to be careful.

Recursion semantics

I am not a fan of what I call "precondition recursion" (I can't find a reference to different styles of recursion, so this is my name for it...). In your case, you are adding the strings to the bucket inside the loop inside the recursive function. I believe you should try to do that only at the "leaf" level of the recursion. Logically, you manipulate all the characters, then, when no more characters can be manipulated, you add the resulting string to the bucket. In the code it will look like:

private static void stringPermutation(char[] strArray, HashSet<String> bucket, int index) {
    if(index == strArray.length) {
        bucket.add(new String(strArray));
        return;
    }

Conclusion

Putting this together, I changed your entry function to be:

public static Collection<String> stringPermutation(String s) {
    Collection<String> perms = new LinkedList<String>();
    stringPermutation(s.toCharArray(), perms, 0);
    return perms;
}

Then, I changed the recursion to:

• only add in the recursion leaf level
• remove the cloning
• add an "unswap" operation

The result is:

private static void stringPermutation(char[] strArray, Collection<String> bucket, int index) {
    if (index == strArray.length) {
        bucket.add(new String(strArray));
        return;
    }

    for (int i = index; i < strArray.length; i++) {
        swapChars(strArray, i, index);
        stringPermutation(strArray, bucket, index + 1);
        swapChars(strArray, i, index);
    }
}

For my own sanity, I put that in to an ideone script here, so you (and I) can see it working: https://ideone.com/9xUeau