# 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.

Problem Description

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

Problem Solution

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.

Program/Source Code

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)```
Program Explanation

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.

Runtime Test Cases
```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.

Note: Join free Sanfoundry classes at Telegram or Youtube

If you find any mistake above, kindly email to [email protected]