It is often interesting to iterate over all permutations of an array. Consider the three letters N, O, W. There are six permutations, and three of them are English words:

Find the rightmost pair of elements that are in ascending order. (If the entire permutation is in descending order, there is no next permutation, and we’re done.) Call this the pivot. Notice that all of the elements from the second element in the pivot to the end of the permutation are in descending order. Call this the tail. Example: C B DG F E A

Find the rightmost element in the tail that is larger than the first element of the pivot. Example: C B DG F E A

Swap this element with the first element of the pivot. Note that the new tail is still in descending order. Example: C B EG F D A

Put the tail in ascending order by reversing it. Example: C B EA D F G

The time this algorithm takes is proportional to the length of the tail. The tail could be as short as a single element, e. g. A B C D E F G => A B C D E GF. Or it could be as long as the whole permutation, minus one, e.g. A G F E D C B => BA C D E F G.

It turns out though that short tails are very, very common, and long tails are very, very, rare. In half of all permutations, the tail length is 1; in half of the remainder, the tail length is 2; in half of the remainder, the tail length is 3, etc. The exponential decay in the count of permutations outweighs the linear growth in the tail length so completely that, on average, you can find the next permutation in constant time (which is less time than it takes to print the result.)

## 2 thoughts on “Iterating over permutations, part 1 – Nariyana Pandita method”