This is a Python program to print all permutations of a string in lexicographic order without using recursion.
The problem is the display all permutations of a string in lexicographic or dictionary order.
1. The algorithm work by first creating a loop that will run n! times where n is the length of the string.
2. Each iteration of the loop prints the string and finds its next permutation to be printed in the next iteration.
3. The next higher permutation is found as follows.
4. If our sequence is called seq, then we find the smallest index p such that all elements in seq[p…end] are in descending order.
5. If seq[p…end] is the entire sequence, i.e. p == 0, then seq is the highest permutation. So we simply reverse the entire string to get the smallest permutation which we consider as the next permutation.
6. If p > 0, then we reverse seq[p…end].
7. Then we look for the smallest element in seq[p…end] that is greater than seq[p – 1] and swap its position with seq[p – 1].
8. This is then the next permutation.
Here is the source code of a Python program to print all permutations of a string in lexicographic order without 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) # there are going to be n! permutations where n = len(seq) for _ in range(factorial(len(seq))): # print permutation print(''.join(seq)) # find p such that seq[p:] is the largest sequence with elements in # descending lexicographic order p = len(seq) - 1 while p > 0 and seq[p - 1] > seq[p]: p -= 1 # reverse seq[p:] seq[p:] = reversed(seq[p:]) if p > 0: # find q such that seq[q] is the smallest element in seq[p:] such that # seq[q] > seq[p - 1] q = p while seq[p - 1] > seq[q]: q += 1 # swap seq[p - 1] and seq[q] seq[p - 1], seq[q] = seq[q], seq[p - 1] 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 lexicographic order.
Case 1: Enter the string: pig pig gip gpi igp ipg pgi Case 2: Enter the string: abcd abcd abdc acbd acdb adbc adcb bacd badc bcad bcda bdac bdca cabd cadb cbad cbda cdab cdba dabc dacb dbac dbca dcab dcba 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.