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 ` `) `

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 `