Day78: Python Program to Print All Permutations of a String in Lexicographic Order without Recursion

 def next_permutation(s):

    s = list(s)

    n = len(s)

    i = n - 2

    while i >= 0 and s[i] >= s[i + 1]:

        i -= 1

    if i == -1: 

        return False

    j = n - 1

    while s[j] <= s[i]:

        j -= 1

    s[i], s[j] = s[j], s[i]

     s = s[:i + 1] + s[i + 1:][::-1]

    return ''.join(s)

def permutations_in_lexicographic_order(string):

    string = ''.join(sorted(string))

    print(string)

 while True:

        string = next_permutation(string)

        if not string:

            break

        print(string)

string = input("Enter a string: ")

print("Permutations in lexicographic order:")

permutations_in_lexicographic_order(string)

#source code --> clcoding.com 

Code Explanation:

1. Function: next_permutation(s)

This function generates the next lexicographic permutation of the string s using an iterative approach.

Step-by-Step Explanation:

def next_permutation(s):

    s = list(s)

    n = len(s)

The input string s is converted into a list because strings are immutable in Python, but lists allow swapping elements.

n stores the length of the string.

Step 1: Find the Largest Index i Where s[i] < s[i + 1]

    i = n - 2

    while i >= 0 and s[i] >= s[i + 1]:

        i -= 1

Start from the second last character (n-2) and move left.

Find the first position i where s[i] < s[i + 1]. This identifies the point where the order needs adjustment.

If no such index i exists (string is in descending order), the function will later return False.

Step 2: Return False if Permutation is the Largest

    if i == -1:

        return False

If i becomes -1, it means the entire string is in descending order, and there are no further permutations.

Return False to indicate no more permutations can be generated.

Step 3: Find the Largest Index j Where s[j] > s[i]

    j = n - 1

    while s[j] <= s[i]:

        j -= 1

Start from the last character (n-1) and move leftward.

Find the smallest character s[j] (to the right of i) that is larger than s[i]. This ensures the next permutation is just slightly larger.

Step 4: Swap s[i] and s[j]

    s[i], s[j] = s[j], s[i]

Swap the characters at indices i and j. This adjusts the order to make the permutation larger.

Step 5: Reverse the Characters to the Right of i

    s = s[:i + 1] + s[i + 1:][::-1]

The characters to the right of i (s[i + 1:]) are reversed.

Reversing creates the smallest lexicographic order for this portion, ensuring the permutation is the next smallest.

Step 6: Return the Updated Permutation

    return ''.join(s)

Convert the list s back into a string and return it as the next permutation.

2. Function: permutations_in_lexicographic_order(string)

This function generates and prints all permutations of the input string in lexicographic order.

Step-by-Step Explanation:

    string = ''.join(sorted(string))

Sort the input string lexicographically (alphabetically) so that permutations start with the smallest order.

For example, "cba" is sorted to "abc".

    print(string)

Print the first permutation (smallest lexicographic order).

Generate and Print Subsequent Permutations

    while True:

        string = next_permutation(string)

        if not string:

            break

        print(string)

Use a loop to repeatedly call the next_permutation function:

If next_permutation returns False, break the loop, as no further permutations are possible.

Otherwise, print the newly generated permutation.

3. Input and Execution

string = input("Enter a string: ")

Prompt the user to enter a string to generate permutations.

print("Permutations in lexicographic order:")

Print a message indicating the start of the permutations.

permutations_in_lexicographic_order(string)

Call the permutations_in_lexicographic_order function to generate and display permutations.