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.
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)
PQRS PQSR PRQS PRSQ PSQR PSRQ QPRS QPSR QRPS QRSP QSPR QSRP RPQS RPSQ RQPS RQSP RSPQ RSQP SPQR SPRQ SQPR SQRP SRPQ SRQP
- If the length of the string is n, then there will be n! permutations. Therefore, create a loop that will run n! times
- In each iteration, one of the permutations is printed in lexicographical order.
- Locate the smallest index ‘i’ such that all the elements in givenstr[i… end] are in non-increasing order.
- if i==0 i.e. current string is the last permutation, so reverse it and print it.
- In the event of i>0, reverse givenstr[i…end].
- 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)
PQR PRQ QPR QRP RPQ RQP
HOPE YOU LIKED THIS TUTORIAL!