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

This is a Python program to print all permutations of a string in lexicographic order without 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 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.

Program/Source Code

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)
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 lexicographic order.

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

Note: Join free Sanfoundry classes at Telegram or Youtube

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

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.