Python | All permutations of a string in lexicographic order without using recursion

lexicographic order | Python functions | sin | String Variables

Michael Zippo 18.07.2021

Examples :

  Input:  python  Output:  hnopty hnopyt hnotpy hnotyp hnoypt ...... ytpnho ytpnoh ytpohn ytponh  Input:  xyz  Output:  xyz xzy yxz yzx zxy zyx

Method 1:
Usage default libraries for permutations of itertools functions.
The permutation function will create all permutations of a given string, and then we sort the result to get the desired result.

from itertools import permutations

def 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! links, where n — the length of the string, since there will be n! Permutations.

Each iteration prints a line and finds the next large lexicographic permutation to be printed in the next iteration.

The next higher permutation is found as:

Let the line be called str, find the smallest index i so 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 tallest permutation. So we just flip the entire line to get the smallest permutation, which we think is the next permutation.

If i" 0, then we return str [i… end].

Then we look for the smallest element in str [i… end] that is greater than str [i — 1], and change its position to str [i — 1].

This is the next permutation.

# library import

from math import factorial

def lexicographical_permutations ( str ):

# will be n! permutations where n = len (seq)

for p in range (factorial ( len ( str ))) :

print (’’. join ( str ))

i = len ( str ) - 1

# find me such that str [i:] is the largest sequence with

# items 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

# swp 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