Find an algorithm (subroutine) that when called repeatedly with the same character-string variable that is initialized with n characters, all different, will cycle through all the permutations of those n characters, so that for example, when called 24 times with a string of length 4, will have cycled that string through all 24 permutations and returned it to its initial state.
I think it's easier to think of this problem in terms of numbers, rather than characters. It's really the same thing--you just think of every character as a digit in a base-(size of character set) number system.
Suppose it wasn't permutations. Suppose you were given a 4-digit number, and told to walk through every 4-digit number until you came back to your starting point. Each iteration doesn't have to yield a permutation of the original number, and leading zeros are allowed. The most straightforward way would be to just keep adding 1 to the input until you reached the highest value, 9999, and then loop back to the smallest value, 0000, and keep going. This gives you every result.
Think about how ordinary counting works. You start at the rightmost digit that you can increase (i.e., the rightmost digit that isn't 9) and you increase it by the smallest amount possible (add 1 to it). Then you set all the digits to the right of that digit to the smallest number available. In this case, it's all zeros. Everything to the left of the digit you increased is unaffected.
That's approximately the approach we'll look for in finding permutations. Find the rightmost digit that you can increase, and increase it by the smallest amount possible. Set the digits to the right of that digit to the smallest value possible. If we get to a number we can't increase, loop around and rearrange the digits to the smallest one possible.
Given an input number, start walking through its digits, starting from the right. In order for us to increase a digit without affecting the digits to its left, we'll have to find a digit A such that some digit to the right of it is larger than A. Note that all the digits to the right of A must be in descending order. Otherwise, our search would have stopped before we got to A. So really all you have to do is start at the rightmost digit and work your way to the left until the digit you're looking at is smaller than the one to the right of it. This is the digit you will be increasing.
Next, we have to figure out what we'll be increasing it
to. We want the smallest digit that is still larger than A. Again, the digits to the right of A are in descending order, so all we have to do is start searching from the right side of the number for a digit larger than A. The first one we find will be the one we want to use. We'll call it B. To increase the digit at A's position, swap A and B.
Remember that all digits to the right of B's former position were smaller than A. Also, since B is larger than A, and all the digits that were between A and B were in descending order, all digits that were between A and B were larger than A. That means that after we swap A and B, A will be in a sequence of digits that is still in descending order. Specifically, all the digits after B will be in descending order after the swap.
The last step is to make all the digits to the right of B represent the smallest number possible. That means the most significant digit must be as small as possible, the one to the right of it must be the smallest digit of those remaining, and so on. In other words, those digits must be in ascending order. Since they are already in descending order, all we have to do is reverse the sequence.
Substitute characters for digits, and that pretty much does it. Here's the C++ code:
void perm(std::string& val)
{
int aPos = val.size() - 2;
while (aPos >= 0)
{
if (val[aPos] < val[aPos + 1])
break;
--aPos;
}
if (aPos < 0)
{
// characters are in descending order
std::reverse(val.begin(), val.end());
return;
}
int bPos = val.size() - 1;
while (val[bPos] < val[aPos])
--bPos;
std::swap(val[aPos], val[bPos]);
std::reverse(val.begin() + aPos + 1, val.end());
}
Solution
