Write a python program to print all the permutations of a string in lexicographical order.
Examples:
Input : python Output : hnopty hnopyt hnotpy hnotyp hnoypt ...... ytpnho ytpnoh ytpohn ytponh Input : xyz Output : xyz xzy yxz yzx zxy zyx
Method 1: Using the default library itertools function permutations. permutations function will create all the permutations of a given string and then we sort the result to get our desired output.
Python
from itertools import permutationsdef lexicographical_permutation(str): perm = sorted(''.join(chars) for chars in permutations(str)) for x in perm: print(x) str ='abc'lexicographical_permutation(str) |
Output :
abc acb bac bca cab cba
Method 2:
- First we create a loop that will run n! ties where n is the length of the string as there will be n! permutations.
- Every iteration prints the string and finds its next larger lexicographical permutation to be printed in the next iteration.
- The next higher permutation is found as :-
- Let the string is called str, find the smallest index i such that all elements in str[i…end] are in descending order.
- If str[i…end] is the entire sequence, i.e. i == 0, then str is the highest permutation. So we simply reverse the entire string to get the smallest permutation which we consider as the next permutation.
- If i > 0, then we reverse str[i…end].
- Then we look for the smallest element in str[i…end] that is greater than str[i – 1] and swap its position with str[i – 1].
- This is then the next permutation.
Python3
# import libraryfrom math import factorial def lexicographical_permutations(str): # there are going to be n ! permutations where n = len(seq) for p in range(factorial(len(str))): print(''.join(str)) i = len(str) - 1 # find i such that str[i:] is the largest sequence with # elements in descending lexicographic order while i > 0 and str[i-1] > str[i]: i -= 1 # reverse str[i:] str[i:] = reversed(str[i:]) if i > 0: q = i # find q such that str[q] is the smallest element # in str[p:] such that str[q] > str[i - 1] while str[i-1] > str[q]: q += 1 # swap str[i - 1] and str[q] temp = str[i-1] str[i-1]= str[q] str[q]= temp s = 'abcd's = list(s)s.sort()lexicographical_permutations(s) |
Output :
abcd abdc acbd acdb adbc adcb bacd badc bcad bcda bdac bdca cabd cadb cbad cbda cdab cdba dabc dacb dbac dbca dcab dcba
Time Complexity: O(n*n!)
Auxiliary Space: O(1)
