There is a devilishly clever algorithm for doing permutations called the Steinhausâ€“Johnsonâ€“Trotter method. The basic idea is fairly simple, but it takes a little bit of work to implement. The algorithm is intended for finding permutations of numbers 1 to n. If you want to use it for a string, just treat the numbers as indices into the string.

The algorithm only swaps adjacent elements. It is best to think of it as running recursively, but the code can be implemented fairly easily without it.

Suppose we want to find permutations of the numbers 1 to 4. Start with the initial position as the first permutation of (1,2,3,4). We are going to move 4 through each permutation of (1,2,3). Moving right to left we get (1,2,4,3 ), (1,4,2,3) and (4,1,2,3). It is stuck and must change direction, but only after we get the next permutation of the numbers 1 to 3.

Now we get the next permutation of (1,2,3). We are going to move 3 through (1,2). This gives (1,3,2).

Now we can move 4 left to right through (1,3,2), giving (4,1,3,2), (1,4,3,2) and (1,3,4,2) and (1,3,2,4). 4 can’t move any further.

We switch back to 3 and again move it once. Eventually, 3 will reach the end or bump against 4. No number can move past a larger number. With 3 being stuck, we go down to 2.

To summarize, the basic idea is this:

1. Starting with n, find first number that is not stuck and transpose it with the next number.

2. Reverse direction of all the numbers that were found to be stuck.

3. Go back to step 1

At some point, all the numbers 2 to n will be stuck, at which point we are done.

Suppose that you want to find all the unique letter permutations of a word. For, example, for test, you want to treat the two t’s as equivalent. The above algorithm makes this easy. For example consider the word test. Our initial permutation is (1,2,3,4) and the indices of the two t’s are (1,4). We say that their degree of disorder is 0. Since the algorithm only transposes adjacent elements, the only way for the t’s to get out of order is if the indices 1 and 4 are being swapped. If the 4 index is going to move ahead of the 1 index, we bump the disorder by 1. Otherwise we decrement by 1. We return string permutations only when the disorder is 0. Only one disorder counter is needed for any number of instances of repeated letters.