How to Print all permutations in sorted (lexicographic) order in Python

In this tutorial, we will see how to find all permutations of a given string in alexicographically sorted manner with Python.

Dictionary is an example of a group of words sorted in a lexicographical manner.

For example:
All the permutations of the word ‘ABC’ are:

1.ABC 2.BAC 3.CAB 4.ACB 5.BCA 6.CBA

Lexicographically sorted permutations are:

1.ABC 2.ACB 3.BAC 4.BCA 5.CAB 6.CBA

Method 1: Using itertools.permutations

import itertools
def fun(s):
    ans=[] # To store all the permutations
    #Finding all permutations
    permutations=itertools.permutations(s,len(s))
    for word in permutations:
        ans.append("".join(word))
    #sorting permutations in lexicographic order
    for i in sorted(ans):
        print(i)

s="PQRS"
fun(s)

OUTPUT:

PQRS
PQSR
PRQS
PRSQ
PSQR
PSRQ
QPRS
QPSR
QRPS
QRSP
QSPR
QSRP
RPQS
RPSQ
RQPS
RQSP
RSPQ
RSQP
SPQR
SPRQ
SQPR
SQRP
SRPQ
SRQP

Method 2

1. If the length of the string is n, then there will be n! permutations. Therefore, create a loop that will run n! times
2. In each iteration, one of the permutations is printed in lexicographical order.
3. Locate the smallest index ‘i’ such that all the elements in givenstr[i… end] are in non-increasing order.
4. if i==0 i.e. current string is the last permutation, so reverse it and print it.
5. In the event of i>0, reverse givenstr[i…end].
6. Look for the smallest element in givenstr[i…end] that is greater than str[i – 1] and swap its position with str[i – 1].

from math import factorial 
    
def fun(s): 
    for i in range(factorial(len(s))):          
        print(''.join(s))   
        p=len(s)-1
        while (p > 0) and (s[p-1] > s[p]):        
            p=p-1
        s[p:] = reversed(s[p:]) 
        if p > 0: 
            q = p 
            while s[p-1] > s[q]:   
                q=q+1
        s[p-1],s[q]=s[q],s[p-1]
    
s = 'PQR'
s = list(s) 
s.sort() 
fun(s)

OUTPUT

PQR
PRQ
QPR
QRP
RPQ
RQP

HOPE YOU LIKED THIS TUTORIAL!
Also read:

itertools.combinations() in Python

itertools.groupby() in Python