Permute all possible string combinations in C++

This function takes in a string, and will permute every possible combination of arrangements of the characters in the string. Because the function simply iterates through every character, it can output duplicate results. In the case of the word “sells”, for example, the first and last s will be swapped, resulting in the same word being output. One lazy way around this would be to store each combination as a key -> value pair using the STL container class map, which would discard any duplicate keys (although it may be more accurate to say that it would replace the value stored at that key, which would be the duplicate word). Another way would be to use the STL container class vector with std::find, however with larger words this may be a less performance-friendly approach than using a map.

I wrote this function in response to this programming challenge. Using the given input of “cat”, this function actually outputs:

tca
atc
cat
tac
cta
act

So, it doesn’t replicate the example output given by the challenge exactly, (same results, different order) however, the requirements were to find all permutations, and repeated outputs in the case of duplicate characters are allowed too, so the function satisfies the challenge requirements.

How it works:

The function contains two loops, with one nested within the other. The outer loop iterates through a single character at a time, executes the inner loop, and then swaps each character with the next character at index i+1. The inner loop takes each character from the back of the string, moves it to the front, and then prints the string to the console. Combining these two processes allows us to permute every possible combination of characters, and the function will work on any size string.

You’ll notice that the outer loop iterates while i is less than str.length()-1, rather than str.length(). Why? Because we’re swapping the character at position i of the string with the character at position i+1 at the bottom of the outer loop, we have to ensure we do not go out of bounds of the string. If we used str.length() instead, then on the last iteration of the outer loop when we assign str[i] = str[i+1];, we’d be attempting to access an index just beyond the length of the string, which would give us undefined behaviour. It could crash the program, access some other data stored in memory, or do nothing at all. In all likelihood it would eventually crash the program.

The outer loop will run while i is less than str.length()-1, so it will stop executing once i is equal to the last index location of the string, preventing us from attempting to access an element beyond the bounds of the string.

We also use str.length()-1 to ensure we assign the last character in the string to buf within the inner loop. The length method of the string class gives the total number of characters in the string, but as the index of a string starts at 0, the last index in the string is equal to str.length()-1

If you’re still not entirely sure how the function works, then try it for yourself. Try commenting out the inner loop entirely and running the code, or see what happens when you don’t swap the character at position i in the string with i+1 in the outer loop.