In this blog post we will examine how we can compute the next lexicographic permutation of a list. We will implement the algorithm in Python 3.4.

1. Problem
We are given a list L of numbers, and we want to find its next lexicographic permutation. For example, let L = [1, 2, 3, 4]. Then the next lexicographic permutation is L = [1, 2, 4, 3]. Below are all 24 permutations in lexicographic order.

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]

How can we compute them?

2. Solution

2.1. Pandit’s algorithm
Wikipedia describes the following algorithm by Narayana Pandit that changes the list in-place to generate the next lexicographic permutation.

1. Find the largest index i such that L[i] < L[i + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index j greater than i such that L[j] > L[i].
3. Swap the value of L[i] with that of L[j].
4. Reverse the sequence from L[i + 1] up to and including the final element L[n - 1], where L is zero-indexed.

2.2. Example
Let us try to understand this algorithm with an example. We will follow this excellent explanation. Consider the list L = [3, 9, 4, 1, 2]. The first three permutations are

[3, 9, 4, 1, 2]
[3, 9, 4, 2, 1]
[4, 1, 2, 3, 9]

We can see that ‘3’ does not change its position in the transition from [3, 9, 4, 1, 2] to [3, 9, 4, 2, 1]. However, in the next transition from [3, 9, 4, 2, 1] to [4, 1, 2, 3, 9] the number ‘3’ changes its position. Why is that?

If you look closely at [3, 9, 4, 2, 1] you can see that all the numbers to the right of ‘3’ are in descending order. This means that there is no next permutation for the sublist [9, 4, 2, 1], so we are forced to do something with the ‘3’. To be exact, we will swap ‘3’ with one of the numbers in that sublist, namely with the next higher number. The next higher number in that sublist is ‘4’, and by swapping ‘3’ and ‘4’ we get [4, 9, 3, 2, 1]. ‘4’ is now in the front.

We next want to generate permutations with ‘4’ in the front, however the sublist [9, 3, 2, 1] to the right of ‘4’ is not the lexicographic smallest for the numbers 9, 3, 2, 1. It is rather the reverse of that sublist. If we reverse that sublist we get [4, 1, 2, 3, 9] which is the smallest lexicographic permutation with ‘4’ in the front. Note also that to the right of ‘4’ the numbers are ascending. And voilà, we are done.

This is exactly what the steps in Pandit’s algorithm do. Below they are shown in more detail.

L = [3, 9, 4, 2, 1] 

__Step 1: find rightmost position i such that L[i] < L[i+1]
Result: i = 0 and L[i] = 3 

__Step 2: find rightmost position j to the right of i such that L[j] > L[i]
Result: j = 2 and L[j] = 4 

__Step 3: swap L[i] and L[j]
Swappping at indices: 0 and 2
Result after swapping: [4, 9, 3, 2, 1] 

__Step 4: reverse everything to the right of i
Result of reversing: [4, 1, 2, 3, 9]

The key to understanding the algorithm was therefore to recognize that the greatest lexicographic permutation of a sublist is reached when it is in descending order, and the smallest lexicographic permutation of a sublist is generated when the items in it are in ascending order.

3. Implementation in Python 3.4

def next_permutation(L):
    '''
    Permute the list L in-place to generate the next lexicographic permutation.
    Return True if such a permutation exists, else return False.
    '''
    
    n = len(L)

    #------------------------------------------------------------

    # Step 1: find rightmost position i such that L[i] < L[i+1]
    i = n - 2
    while i >= 0 and L[i] >= L[i+1]:
        i -= 1
    
    if i == -1:
        return False

    #------------------------------------------------------------

    # Step 2: find rightmost position j to the right of i such that L[j] > L[i]
    j = i + 1
    while j < n and L[j] > L[i]:
        j += 1
    j -= 1
    
    #------------------------------------------------------------

    # Step 3: swap L[i] and L[j]
    L[i], L[j] = L[j], L[i]
    
    #------------------------------------------------------------

    # Step 4: reverse everything to the right of i
    left = i + 1
    right = n - 1

    while left < right:
        L[left], L[right] = L[right], L[left]
        left += 1
        right -= 1
            
    return True

Here is an example:

def example():
    L = [1, 2, 3]

    while True:
        print(L)
        if not next_permutation(L):
            break


#----------------------------------------------------------------

if __name__ == "__main__":
    example()

The output is:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

References
1. Algorithm to find next greater permutation of a given string – dicussion on Stackoverflow.
2. Generation of permutations in lexicographic order – Wikipedia article.
3. std::next_permutation Implementation Explanation – discussion on Stackoverflow.

Exercises

1. Solve the problem NEXTPERM on SPOJ.

2. Print all the permutations of the string “000111” in lexicographic order.

3. You are given the set S = {2, 3, 5, 7, 11, 13, 17}. Now, consider all 4-element subsets of S. How many of those subsets have the property that the sum of their elements is greater than 20. For example, the sum of the elements in the subset {7, 11, 13, 17} is greater than 20, however the sum of the elements in the subset {2, 3, 5, 7} is not greater than 20.

4. Solve the problems above by using the built-in function std::next_permutation in C++.

Solution to exercise 3
Here are three methods to solve this problem. All of them return the result 34. The set is stored as a list L = [2, 3, 5, 7, 11, 13, 17].

Method 1
We use four for-loops to simulate four pointers i, j, k and m that move over L, and we calculate the sum L[i] + L[j] + L[k] + L[m].

def method1():
    L = [2, 3, 5, 7, 11, 13, 17]
    n = len(L)

    cnt = 0
    for i in range(n-3):
        for j in range(i+1, n-2):
            for k in range(j+1, n-1):
                for m in range(k+1, n):
                    if L[i] + L[j] + L[k] + L[m] > 20:
                        cnt += 1
    return cnt

Method 2
We use itertools.combinations to iterate over all 4-element subsets.

def method2():
    L = [2, 3, 5, 7, 11, 13, 17]
    cnt = 0
    
    from itertools import combinations
    for subset in combinations(L, 4):
        if sum(subset) > 20:
            cnt += 1
            
    return cnt

Method 3
We finally use our function next_permutation. The trick is to generate all permutations of the list [0, 0, 0, 1, 1, 1, 1] which serve as bitmasks. A bitmask tells us which items in L we pick, namely those ones where the bitmask is set to 1. For example, the bitmask [1, 0, 0, 0, 1, 1, 1] tells us to pick the items at positions 0, 4, 5 and 6. See also exercise 2.

def method3():
    L = [2, 3, 5, 7, 11, 13, 17]
    bitmask = [0, 0, 0, 1, 1, 1, 1]
    cnt = 0
    
    while True:
        sum_subset = sum( a*b for a,b in zip(L, bitmask) )
        if sum_subset > 20:
            cnt += 1
        if not next_permutation(bitmask):
            break

    return cnt

To calculate the sum of elements in a subset we calculate the dot product between L and bitmask via sum( a*b for a,b in zip(L, bitmask) )