Change language

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

| | |

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 )


 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)


     abcd abdc acbd acdb adbc adcb bacd badc bcad bcda bdac bdca cabd cadb cbad cbda cdab cdba dabc dacb dbac dbca dcab dcba