Iterating over permutations, part 1 – Nariyana Pandita method

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:

  • NOW
  • NWO
  • ONW
  • OWN
  • WNO
  • WON

I found three different algorithms to iterate over permutations and implemented them all in PowerShell. Also see Iterating over permutations, part 2 – Heap’s algorithm and Iterating over permutations, part 3 – Steinhaus-Johnson-Trotter algorithm.

In India in the 1300s, mathematician Nariyana Pandita described a method to find the next permutation in alphabetical order, starting from a given permutation:

  1. 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 D G F E A
  2. Find the rightmost element in the tail that is larger than the first element of the pivot.
    Example: C B D G F E A
  3. Swap this element with the first element of the pivot. Note that the new tail is still in descending order.
    Example: C B E G F D A
  4. Put the tail in ascending order by reversing it.
    Example: C B E A 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 G F. Or it could be as long as the whole permutation, minus one, e.g. A G F E D C B => B A 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s