Python Program to Print All Permutations of a String in Lexicographic Order using Recursion

This is a Python program to print all permutations of a string in lexicographic order using recursion.

The problem is the display all permutations of a string in lexicographic or dictionary order.

1. The algorithm work by creating a recursive function get_next_permutation that returns the next higher permutation of a sequence seq. If seq is the highest permutation then it returns None.
2. The function get_next_permutation first tests the case where seq is the empty list. If it is, it returns None.
3. Then it calls get_next_permutation on seq[1:]. Let the return value be nxt.
4. If nxt is not None, then the next higher permutation of seq is simply the concatenation of [seq[0]] and nxt.
5. If nxt is None, then seq[1:] is in descending order and is the highest permutation.
6. To find the next higher permutation, we first reverse seq[1:].
7. Then we look for the smallest element in seq[1…end] that is greater than seq[0] and swap its position with seq[0].
8. This is the next higher permutation which is then returned.
9. If we cannot find an element greater than seq[0] then the entire sequence is in descending order and so seq is the highest permutation. In this case, None is returned.

Here is the source code of a Python program to print all permutations of a string in lexicographic order using recursion. The program output is shown below.

from math import factorial
 
def print_permutations_lexicographic_order(s):
    """Print all permutations of string s in lexicographic order."""
    seq = list(s)
    for _ in range(factorial(len(seq))):
        print(''.join(seq))
        nxt = get_next_permutation(seq)
        # if seq is the highest permutation
        if nxt is None:
            # then reverse it
            seq.reverse()
        else:
            seq = nxt
 
def get_next_permutation(seq):
    """Return next greater lexicographic permutation. Return None if cannot.
 
    This will return the next greater permutation of seq in lexicographic
    order. If seq is the highest permutation then this will return None.
 
    seq is a list.
    """
    if len(seq) == 0:
        return None
 
    nxt = get_next_permutation(seq[1:])
 
    # if seq[1:] is the highest permutation
    if nxt is None:
        # reverse seq[1:], so that seq[1:] now is in ascending order
        seq[1:] = reversed(seq[1:])
 
        # find q such that seq[q] is the smallest element in seq[1:] such that
        # seq[q] > seq[0]
        q = 1
        while q < len(seq) and seq[0] > seq[q]:
            q += 1
 
        # if cannot find q, then seq is the highest permutation
        if q == len(seq):
            return None
 
        # swap seq[0] and seq[q]
        seq[0], seq[q] = seq[q], seq[0]
 
        return seq
    else:
        return [seq[0]] + nxt
 
 
s = input('Enter the string: ')
print_permutations_lexicographic_order(s)

1. The user is asked to enter a string.
2. The function print_permutations_lexicographic_order is called on the string.
3. The function then prints all permutations of the string in order.

Case 1:
cow
cwo
ocw
owc
wco
woc
 
Case 2:
Enter the string: dogs
dogs
dosg
dsgo
dsog
gdos
gdso
gods
gosd
gsdo
gsod
odgs
odsg
ogds
ogsd
osdg
osgd
sdgo
sdog
sgdo
sgod
sodg
sogd
ogds
ogsd
 
Case 3:
Enter the string: a
a

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.