## C++ Algorithms: next_permutation

### Mark Nelson

On the elegance of next_permutation, which might even help you with your homework, by the way.

My daughter’s math teacher at Hockaday School in Dallas wants his sixth-grade students to enjoy their class. He’s 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. That’s 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 I’d 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 isn’t 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.)

## Magic Permutations

From this program, you can see that

next_permutationis 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 makesnext_permuationinteresting 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_permuationwill always generate the next set in the series given only the previous one as input.Just writing a function to generate permutations isn’t particularly hard. One easy way to tackle the problem is with a recursive approach. If the string you want to permute is

ncharacters long, you execute a loop that makesnpasses — one pass per character in the string. Each timeipasses through the loop, you remove characterifrom 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 don’t 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 theacharacter and then get the permutations of"bc". To get those permutations, you first strip off thebcharacter and get a resulting permutation list of"c". Concatenating with the prefix characterbresults in the permutation"bc". You then strip off theccharacter and get a resulting permutation list of"b". Concatenating with the prefix charactercresults in the permutation"cb". The results when combined with the prefix characteragive strings"abc"and"acb". You then repeat the process for prefixband substring"ac"and then for prefixcand substring"ab".Using the C++ Standard library’s 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_permutationmanages 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_permutationwill work its way through all possible permutations of the sequence, eventually returning a value offalsewhen there are no more permutations left.

## Internals of next_permutation

You don’t need to be an STL expert to understand this code, but if you’ve 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

BidirectionalIteratortype 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 iteratorsfirstandlast.firstpoints to the first element in the sequence, whilelastpoints one past the last element. The code shown in Listing 3 also uses two other STL functions:iter_swapswaps the values pointed to by its two arguments, andreversesimply 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, I’ve 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

falseif it finds either. Naturally, sequences of those lengths only have one permutation, so they must always returnfalse. 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 membernis less than membern+1. These members are pointed to by iteratorsiandiirespectively. If the function doesn’t 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

iandiihave 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 byi. Because of the previous search foriandii, you know that at worst the search will end atii, but it might end earlier. Once this member is located, it is pointed to by iteratorj.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 byiandj. Finally, a call is made toreverse( ii, last ). This reverses the sequence that starts atiiand ends at the end of the sequence. The end result is a routine that is short, simple, and runs in linear time. You really can’t 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 iteratorsiandii. (Remember that you are searching from the end of the sequence for the first adjacent pair for which the value pointed to byiis less than the value pointed to byii, andiis one less thanii.) The first pair of values that meet the test are seen whenipoints to3andiipoints to5. After that, a second search starts from the end for the first value ofjwherejpoints to a greater value than that pointed to byi. This is seen whenjpoints to4. Once these three iterators are set, there are only two tasks left to perform. The first is to calliter_swap( i, j ), which swaps the values pointed to by the iteratorsiandj. After the function does this, you are left with the modified sequence"24531". The last step is to callreverse( ii, last ), which reverses the sequence starting atiiand 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 tonext_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 doesn’t know or care that there are a huge number of identical permutations in the output sequence. It’s easy to see why the brute force code in Listing 2 doesn’t notice the duplicates. It never pays any attention to the contents of the string that it is permuting. It couldn’t 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, iteratorsiandiiwere initially set to offsets of1and2within the string. But in this case, since the value pointed to byimust be less than the value pointed to byii, the two iterators have to be decremented to positions0and1.jwould again point to position3. 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 position0; 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.

## Conclusion

The addition of the STL to the C++ Standard library gave us a nice grab bag of functions that automate many routine tasks.

next_permuationturned 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 Nelsonis a programmer for Cisco Systems in Richardson, Texas. He is presently working on IP Telephony projects for Cisco. You can reach Mark atmarkn@ieee.orgor via his website at <www.dogma.net/markn>.