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) return total_permutations # 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:

**Input**: The program starts by taking a single input, which is the string for which we want to generate permutations.**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.**Sort Characters**: We sort the characters in the list in lexicographic order. This is done to ensure that we generate permutations in lexicographic order.**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.**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.**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`

.**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.

- We iterate through the characters in
**Generate Permutations**: We call the`generate_permutations`

function with the sorted list of characters, which starts the recursive process of generating all permutations.**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.

## Leave a Review