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] 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 and swap its position with seq.
8. This is the next higher permutation which is then returned.
9. If we cannot find an element greater than seq 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 q = 1 while q < len(seq) and seq > seq[q]: q += 1 # if cannot find q, then seq is the highest permutation if q == len(seq): return None # swap seq and seq[q] seq, seq[q] = seq[q], seq return seq else: return [seq] + 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.