C++ Algorithms: next_permutation
On the elegance of next_permutation, which might even help you with your homework, by the way.
My daughters math teacher at Hockaday School in Dallas wants his sixth-grade students to enjoy their class. Hes fond of sending home interesting problems that are meant to be both entertaining and enriching. As most parents probably know, this can only mean trouble! Last week, Mr. Bourek sent home a worksheet containing a set of variations on the traditional magic square. Students were given various shapes, such as triangles, stars, etc., and asked to fill in a set of consecutive numbers at the vertices. The goal was to come up with an arrangement of numbers such that various rows, columns, and diagonals all added up to a given sum. Kaitlin worked her way through most of the problems in fairly quick order. But the shape shown in Figure 1 managed to stump her.
The problem was simple enough. All she had to do was place the numbers one through nine in the nine positions of the figure so that the sum of all the straight lines was 17. Although Kaitlin was able to knock the other problems out quickly, this one was still unsolved after 15 minutes well past the normal sixth-grade attention span. Even worse, after another 10 minutes of my help, we were no closer to a solution. Thats when I decided it was time for a brute force approach. I remembered that the Standard C++ library had a handy function, next_permutation, that would let me iterate through all the possible arrangements of the figure with just a couple of lines of code. All I had to do was check the five different sums for each permutation and Id have the answer in no time.
The resulting program is shown in Listing 1, and its output is given below:
100706 : 3 5 9 8 2 1 6 4 7 114154 : 3 8 6 5 2 4 9 1 7 246489 : 7 1 9 4 2 5 6 8 3 259937 : 7 4 6 1 2 8 9 5 3 362880 permutations were tested
A little quick sketching will show you that the four solutions are simply rotations and mirror images of the one true solution. You can also see that randomly putting down numbers makes the odds almost 100,000:1 against finding a solution. Not quite as bad as the lottery, but it clearly shows that random guessing isnt going to work. (Kaitlin asked me to give her the center position only, upon which she solved the rest of it in roughly 30 seconds.)
From this program, you can see that next_permutation is a handy function to have in the C++ library. In my case, it meant the difference between writing an impulse program versus fiddling around with pencil and paper for another hour. What really makes next_permuation interesting to me is the fact that it can generate permutations without keeping any additional information beyond the sequence being juggled. I can generate a permutation, go off, and do whatever I like with it, even write the numbers out to a file and save them for later. Regardless of what I do, next_permuation will always generate the next set in the series given only the previous one as input.
Just writing a function to generate permutations isnt particularly hard. One easy way to tackle the problem is with a recursive approach. If the string you want to permute is n characters long, you execute a loop that makes n passes one pass per character in the string. Each time i passes through the loop, you remove character i from the string and keep it as a prefix. You then print out all the permutations of the remaining substring concatenated with the prefix character. To generate the permutations of the substring, you recursively call the permutation function. The only additional piece of logic required is a test to see if a substring is only one character long. If it is, you dont need to call the permutation function, because you already have the only permutation of the substring.
For example, to print the permutations of "abc", you first strip off the a character and then get the permutations of "bc". To get those permutations, you first strip off the b character and get a resulting permutation list of "c". Concatenating with the prefix character b results in the permutation "bc". You then strip off the c character and get a resulting permutation list of "b". Concatenating with the prefix character c results in the permutation "cb". The results when combined with the prefix character a give strings "abc" and "acb". You then repeat the process for prefix b and substring "ac" and then for prefix c and substring "ab".
Using the C++ Standard librarys string class makes it fairly easy to implement this logic. Listing 2 shows the program permute.cpp, which implements this algorithm relatively faithfully. This approach to generating permutations is okay, but its recursive nature makes it unattractive for use in a library. A library user wants to repeatedly call a function that returns a permutation and then do something with the returned value. The code in Listing 2 won't work in this paradigm there's no way to return from deep inside the nested loop without losing the entire context the algorithm uses to generate permutations. next_permutation manages to avoid this trouble by using a simple algorithm that can sequentially generate all the permutations of a sequence (in the same order as the algorithm I described above) without maintaining any internal state information.
The first time I saw this code was in the original STL (Standard Template Library) published by Alexander Stepanov and Ming Lee at Hewlett-Packard. The original code is shown in Listing 3. Using this function is simple. You call it repeatedly, asking it to permute a given sequence. If you start with a sequence in ascending order, next_permutation will work its way through all possible permutations of the sequence, eventually returning a value of false when there are no more permutations left.
Internals of next_permutation
You dont need to be an STL expert to understand this code, but if youve never been exposed to this new part of the C++ Standard library, there are a few things you need to know. First, iterators (and the BidirectionalIterator type used here) are an STL abstraction of pointers. When looking at this code, you can think of the iterators as pointers. The permutation sequence is defined by iterators first and last. first points to the first element in the sequence, while last points one past the last element. The code shown in Listing 3 also uses two other STL functions: iter_swap swaps the values pointed to by its two arguments, and reverse simply reverses the sequence defined by its two arguments. By convention of course, the first argument points to the start of the sequence to be reversed, and the last argument points one past the end of the sequence.
To help illustrate the workings of this algorithm, Ive included a listing of a permutation sequence in Figure 2. It contains all 120 permutations of a five-digit sequence. With this output example, plus Listing 3, it is fairly easy to see how this code works. The function first does a cursory check for sequences of length zero or one and returns false if it finds either. Naturally, sequences of those lengths only have one permutation, so they must always return false. After passing those tests, the algorithm goes into a search loop. It starts at the end of the sequence and works its way towards the front, looking for two consecutive members of the sequence for which member n is less than member n+1. These members are pointed to by iterators i and ii respectively. If the function doesnt find two values that pass this test, it means all permutations have been generated. You can see this in Figure 2 for the very last value, 54321.
Once iterators i and ii have been properly located, there are still a few more steps left. The next step is to again start searching from the end of the sequence for the first member that is greater than or equal to the member pointed to by i. Because of the previous search for i and ii, you know that at worst the search will end at ii, but it might end earlier. Once this member is located, it is pointed to by iterator j.
Once these three iterators are located, there are only two more simple steps. First, a call is made to iter_swap( i, j ). This call simply swaps the members pointed to by i and j. Finally, a call is made to reverse( ii, last ). This reverses the sequence that starts at ii and ends at the end of the sequence. The end result is a routine that is short, simple, and runs in linear time. You really cant ask for much more than that.
Walking through an Example
For a quick look at the algorithm in action, consider what happens when you call next_permutation( "23541" ). After passing through the initial size tests, the algorithm will search for suitable values for iterators i and ii. (Remember that you are searching from the end of the sequence for the first adjacent pair for which the value pointed to by i is less than the value pointed to by ii, and i is one less than ii.) The first pair of values that meet the test are seen when i points to 3 and ii points to 5. After that, a second search starts from the end for the first value of j where j points to a greater value than that pointed to by i. This is seen when j points to 4. Once these three iterators are set, there are only two tasks left to perform. The first is to call iter_swap( i, j ), which swaps the values pointed to by the iterators i and j. After the function does this, you are left with the modified sequence "24531". The last step is to call reverse( ii, last ), which reverses the sequence starting at ii and finishing at the end of the sequence. This yields "24135". Figure 2 shows that the result demonstrated here does agree with the output of the program.
An Additional Charming Attribute
The algorithm shown here has one additional feature that is quite useful. It properly generates permutations when some of the members of the input sequence have identical values. For example, when I generate all the permutations of "ABCDE", I will get 120 unique character sequences. But when I generate all the permutations of "AAABB", I only get 10. This is because there are six different identical permutations of "AAA", and two identical permutations of "BB". When I run this input set through a set of calls to next_permutation, I see the correct output:
AAABB AABAB AABBA ABAAB ABABA ABBAA BAAAB BAABA BABAA BBAAA
This might have you scratching your head a bit. How does the algorithm know that there are six identical permutations of "AAA"? The recursive implementation of a permutation generator I showed in Listing 2 treats the permutations of "AAABB" just as it does "ABCDE", obligingly printing out 120 different sequences. It doesnt know or care that there are a huge number of identical permutations in the output sequence. Its easy to see why the brute force code in Listing 2 doesnt notice the duplicates. It never pays any attention to the contents of the string that it is permuting. It couldnt possibly notice that there were duplicates. It just merrily swaps characters without paying any attention to their value. The STL algorithm, on the other hand, actually performs comparisons of the elements that it is interchanging and uses their relative values to determine what interchanging will be done. In the example from the last section, you saw that an input of "24531" will generate a next permutation of "24135". What if the string had a pair of duplicates, as in "24431"? If the algorithm were ignorant of character values, the next permutation would undoubtedly be "24134". In the previous case, iterators i and ii were initially set to offsets of 1 and 2 within the string. But in this case, since the value pointed to by i must be less than the value pointed to by ii, the two iterators have to be decremented to positions 0 and 1. j would again point to position 3. The subsequent swap operation yields "34421", and the reverse function produces a final result of "31244". Remember that the algorithm works by progressively bubbling the larger values of the string into position 0; you can see that this permutation has already jumped well ahead of the permutation of "24531" on its way to completion. Thus, the algorithm knows how to deal with duplicate values.
The addition of the STL to the C++ Standard library gave us a nice grab bag of functions that automate many routine tasks. next_permuation turned out to be just what I needed to solve a sixth-grade math problem. It might be time for you to look through the declarations in the <algorithm> header file to see what else the standards committee laid on our doorstep.
Mark Nelson is a programmer for Cisco Systems in Richardson, Texas. He is presently working on IP Telephony projects for Cisco. You can reach Mark at firstname.lastname@example.org or via his website at <www.dogma.net/markn>.