Python Program to Print All Permutations of a String in Lexicographic Order without Recursion
Strings in Python:
Strings are simple text in programming, which might be individual letters, words, phrases, or whole sentences. Python strings have powerful text-processing capabilities, such as searching and replacing characters, cutting characters, and changing case. Empty strings are written as two quotations separated by a space. Single or double quotation marks may be used. Three quote characters can be used to easily build multi-line strings.
Given a string ,the task is to print all the permutations of the given string in lexicographic order without using recursion in Python.
Examples:
Example1:
Input:
given string ='hug'
Output:
printing all [ hug ] permutations : hug ugh uhg ghu guh hgu
Example2:
Input:
given string ='tork'
Output:
printing all [ tork ] permutations : tork trko trok kort kotr krot krto ktor ktro okrt oktr orkt ortk otkr otrk rkot rkto rokt rotk rtko rtok tkor tkro tokr
Program to Print All Permutations of a String in Lexicographic Order without Recursion
Below are the ways to Print All string permutations without recursion in lexicographic order:
Have you mastered basic programming topics of java and looking forward to mastering advanced topics in a java programming language? Go with these ultimate Advanced java programs examples with output & achieve your goal in improving java coding skills.
1)Using for and while Loops(Static Input)
Approach:
- Give the string as static input.
- The algorithm works by first generating a loop that will run n! times, where n is the length of the string.
- Each loop iteration produces the string and looks for its next variant to print in the following iteration.
- The following is the next higher permutation.
- If we call our sequence seq, we identify the least index p such that all entries in seq[p…end] are in decreasing order.
- If seq[p…end] represents the whole sequence, i.e. p == 0, then seq is the highest permutation. So we simply reverse the entire string to find the shortest permutation, which we regard to be the next permutation.
- If p > 0, we reverse seq[p…end].
Below is the implementation:
from math import factorial
def printPermutationsLexico(string):
# In lexicographic sequence, print all permutations of string s.
stringseq = list(string)
# There will be n! permutations where n = len (seq).
for t in range(factorial(len(stringseq))):
# print permutation by joining all the characters using join() function
print(''.join(stringseq))
# Find p such that seq[per:] is the longest sequence with lexicographic
# elements in decreasing order.
per = len(stringseq) - 1
while per > 0 and stringseq[per - 1] > stringseq[per]:
per -= 1
# reverse the stringsequence from per to end using reversed function
stringseq[per:] = reversed(stringseq[per:])
if per > 0:
# Find q such that seq[q] is the smallest element in seq[per:] and seq[q] is greater
# than seq[p - 1].Find q such that seq[q] is the smallest
# element in seq[per:] and seq[q] is greater than seq[per - 1].
q = per
while stringseq[per - 1] > stringseq[q]:
q += 1
# swapping seq[per - 1] and seq[q]
stringseq[per - 1], stringseq[q] = stringseq[q], stringseq[per - 1]
# given string as static input
given_string = 'hug'
# printing all the perumutations
print('printing all [', given_string, '] permutations :')
# passing given string to printPermutationsLexico function
printPermutationsLexico(given_string)
Output:
printing all [ hug ] permutations : hug ugh uhg ghu guh hgu
Explanation:
- User must give string input as static .
- On the string, the method printPermutationsLexico is called.
- The function then prints the string’s permutations in lexicographic order.
2)Using for and while Loops(User Input)
Approach:
- Enter some random string as user input using int(input()) function.
- The algorithm works by first generating a loop that will run n! times, where n is the length of the string.
- Each loop iteration produces the string and looks for its next variant to print in the following iteration.
- The following is the next higher permutation.
- If we call our sequence seq, we identify the least index p such that all entries in seq[p…end] are in decreasing order.
- If seq[p…end] represents the whole sequence, i.e. p == 0, then seq is the highest permutation. So we simply reverse the entire string to find the shortest permutation, which we regard to be the next permutation.
- If p > 0, we reverse seq[p…end].
Below is the implementation:
from math import factorial
def printPermutationsLexico(string):
# In lexicographic sequence, print all permutations of string s.
stringseq = list(string)
# There will be n! permutations where n = len (seq).
for t in range(factorial(len(stringseq))):
# print permutation by joining all the characters using join() function
print(''.join(stringseq))
# Find p such that seq[per:] is the longest sequence with lexicographic
# elements in decreasing order.
per = len(stringseq) - 1
while per > 0 and stringseq[per - 1] > stringseq[per]:
per -= 1
# reverse the stringsequence from per to end using reversed function
stringseq[per:] = reversed(stringseq[per:])
if per > 0:
# Find q such that seq[q] is the smallest element in seq[per:] and seq[q] is greater
# than seq[p - 1].Find q such that seq[q] is the smallest
# element in seq[per:] and seq[q] is greater than seq[per - 1].
q = per
while stringseq[per - 1] > stringseq[q]:
q += 1
# swapping seq[per - 1] and seq[q]
stringseq[per - 1], stringseq[q] = stringseq[q], stringseq[per - 1]
# Enter some random string as user input using int(input()) function.
given_string =input('Enter some random string = ')
# printing all the perumutations
print('printing all [', given_string, '] permutations :')
# passing given string to printPermutationsLexico function
printPermutationsLexico(given_string)
Output:
Enter some random string = epic printing all [ epic ] permutations : epic icep icpe iecp iepc ipce ipec pcei pcie peci peic pice piec ceip cepi ciep cipe cpei cpie ecip ecpi eicp eipc epci
Related Programs:
