# Python Program to Print All Permutations of a String in Lexicographic Order using Recursion

In this Python program, we embark on an exploration of permutations and lexicographic ordering. We will employ the power of recursion to generate and display all permutations of a given string in lexicographic order. Recursion, a programming technique where a function calls itself, is well-suited for solving such problems, as it naturally mirrors the recursive nature of permutations.

## Problem Statement

You are tasked with writing a Python program that generates and prints all permutations of a given string in lexicographic order using recursion.

## Python Program to Print All Permutations of a String in Lexicographic Order using Recursion

```def get_lexicographic_permutations(s):
# Convert the string to a list of characters for easier manipulation
char_list = list(s)

# Sort the characters in lexicographic order
char_list.sort()

# Initialize variables to keep track of the current permutation and the total number of permutations
current_permutation = ''.join(char_list)
total_permutations = [current_permutation]

# Recursive function to generate permutations
def generate_permutations(char_list):
nonlocal current_permutation
nonlocal total_permutations

for i in range(len(char_list)):
# Swap the current character with the first character in the remaining string
char_list[0], char_list[i] = char_list[i], char_list[0]

# Generate permutations for the remaining characters
remaining_chars = char_list[1:]
remaining_chars.sort()  # Sort the remaining characters
current_permutation = char_list[0] + ''.join(remaining_chars)

# Add the current permutation to the list of permutations
total_permutations.append(current_permutation)

# Recursively generate permutations for the remaining characters
generate_permutations(remaining_chars)

# Restore the original order of characters for backtracking
char_list[0], char_list[i] = char_list[i], char_list[0]

generate_permutations(char_list)

# Input a string
input_string = input("Enter a string: ")

# Get and print lexicographically sorted permutations
permutations = get_lexicographic_permutations(input_string)
print("Lexicographically sorted permutations:")
for permutation in permutations:
print(permutation)
```

## How it works

To generate all permutations of a string in lexicographic order using recursion, we’ll break down the problem into smaller, manageable steps. Here’s how the program works step by step:

1. Input: The program starts by taking a single input, which is the string for which we want to generate permutations.
2. Convert to List: We convert the input string into a list of characters. This list will make it easier to manipulate the characters during the permutation generation process.
3. Sort Characters: We sort the characters in the list in lexicographic order. This is done to ensure that we generate permutations in lexicographic order.
4. Initialization: We initialize a list, `total_permutations`, to store all permutations, and a variable, `current_permutation`, to store the current permutation being generated. Initially, `current_permutation` is set to the sorted input string.
5. Recursive Function: We define a recursive function, `generate_permutations(char_list)`, that takes the list of characters as an argument. This function generates permutations recursively.
6. Base Case: The base case of the recursion is when there’s only one character left in `char_list`. At this point, we’ve generated a permutation, so we add `current_permutation` to the list of `total_permutations`.
7. Permutation Generation:
• We iterate through the characters in `char_list`, and for each character:
• We swap it with the first character in `char_list`.
• We generate permutations for the remaining characters (excluding the first character), which are stored in `remaining_chars`.
• We sort `remaining_chars` to ensure they are in lexicographic order.
• We update `current_permutation` with the first character followed by `remaining_chars`.
• We add `current_permutation` to the list of `total_permutations`.
• We make a recursive call to `generate_permutations` with the `remaining_chars`.
• After the recursive call, we restore the original order of characters by swapping them back.
8. Generate Permutations: We call the `generate_permutations` function with the sorted list of characters, which starts the recursive process of generating all permutations.
9. Output: Finally, we print the `total_permutations` list, which contains all permutations of the input string in lexicographic order.

The recursion ensures that all possible combinations of characters are explored, leading to the generation of all permutations. Sorting the characters and carefully manipulating them during the recursion guarantees that the permutations are produced in lexicographic order.