## 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.