How to Get All Permutations of a String

Introduction

We want to calculate all the possible permutations of a string. A permutation is a new string, containing the same elements but with a different displacement.

Problem Example

Consider the string “ABC”. Its permutations are:

• ABC
• ACB
• BAC
• BCA
• CBA
• CAB

In the next section, we will see an algorithm written in Java to calculate the permutations of the above string of characters.

Calculate All Permutations of a String

The problem can be approached recursively:

• We define a recursive function taking the string “ABC” as an array of characters, the start index, and the last index as the length of the array minus 1.
• The base case is when the start and last index are equal. When this happens we have a permutation and we print it.
• Otherwise, we do a cycle from the start to the last index, and for each step:
  • We swap characters placed on the left and the current value of the index
  • We call the function recursively adding 1 to the start index
  • We swap the characters again.

The steps described above can be implemented like the following code snippet:

private void performAllPermutations(char[] characters, int left, int rigth) {
    if (left == rigth) {
        System.out.println(characters);
    } else {
        for (int i = left; i <= rigth; i++) {
            characters = swapCharacters(characters, left, i);
            performAllPermutations(characters, left + 1, rigth);
            characters = swapCharacters(characters, left, i);
        }
    }
}

@Test
public void stringPermutationTest() throws Exception {
    String toPermute = "ABC";
    char[] toPermuteArray = toPermute.toCharArray();
    performAllPermutations(toPermuteArray, 0, toPermuteArray.length - 1);
}

public char[] swapCharacters(char[] characters, int i, int j) {
    char temp = characters[i];
    characters[i] = characters[j];
    characters[j] = temp;
    return characters;
}

Permutations of a String: Performance Considerations

The time complexity of the above algorithm is in general O(n*n!), since each permutation costs a factorial term, as we know from combinatory mathematics, and must be repeated n times.

Conclusion

In this article, we have seen how to calculate all the possible permutations of a string. The example code is available on GitHub.