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

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 )

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 & gt; 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 & gt;  0 and str [i - 1 ] & gt;  str [i]: 

    i - = 1

     

    # reverse str [i:]

      str [i:] = reversed ( str [i:]) 

     

     

    if i & gt;  0 :

     

    q = i

    # find q such that str [q] is the smallest element

    # in str [p:] such that str [q] & gt; str [i - 1]

    while str [i - 1 ] & gt;  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