Next Lexicographical Permutation

We all learned permutations and combinations in high school, it’s all about that whether order matters or not, counting the number of permutations and combinations of size N.

There’s the question that we faced: List all the permutations of size 3.  You go with:

  • (1,2,3)
  • (3,1,2) – shifting the numbers to the right
  • (2,3,1) – again
  • (1,3,2) – swap first and last number
  • (2,1,3) – shift the numbers to the right
  • (3,2,1) – again
  • Done.

This approach is naive.  Surely you can implement this approach via recursion, and swapping when it hits the base case (when the permutation has already been listed).  Recursion should not be used in most languages.  The majority of imperative programming language (e.g. Python, C++, Java, Ruby) vastly uses iteration over recursion.  This is because recursion requires space in the stack memory and it takes time to skip duplicate values.  When they run out of stack memory, the program crashes due to stack overflow.

The key in implementing it is to increase the sequence with minimal change.  It is similar to counting up, where we change the rightmost number while trying to preserve the number on its left when possible.

The algorithm implementation below is based on Wikipedia’s Generation in lexicographic order:

  1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
  2. Find the largest index l greater than k such that a[k] < a[l].
  3. Swap the value of a[k] with that of a[l].
  4. Reverse the sequence from a[k + 1] up to and including the final element a[n].
# Computes the next lexicographical permutation of the specified list in place,
# returning whether a next permutation existed. (Returns False when the argument
# is already the last possible permutation.)
#

# Author: Ionwyn

from math import factorial

def sucessor(arr):
    # Find largest increasing index
    k = len(arr) - 1
    while k > 0 and arr[k - 1] >= arr[k]:
        k -= 1
    if k <= 0:
        return "Array given is the last permutation."
    
    # Find successor to arr[k]
    l = len(arr) - 1
    while arr[l] <= arr[k - 1]:
        l -= 1

    # Swap arr[k] with arr[l]
    arr[k - 1], arr[l] = arr[l], arr[k - 1]
    
    # Reverse arr[k+1] up to and including final element arr[n]
    arr[k : ] = arr[len(arr) - 1 : k - 1 : -1]
    print arr

# Lists all lexicographic permutation of size N.
def list_all(n):
    arr = range(1,n+1)

    print arr
    for i in range(1, factorial(n)):
        next_permutation(arr)

Illustration of what’s happening:

next-permutation-algorithm

As expected from the code:

>>> next_permutation([0,1,2,5,3,3,0])
[0, 1, 3, 0, 2, 3, 5]
>>> list_all(3)
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s