Python Program to Generate All Permutations of a Given String
This document provides a Python program that generates all permutations of a given string. The program uses recursion to achieve this and includes detailed explanations and documentation for each part of the code.
Program Explanation
The program uses a recursive function to generate all permutations of a given string. The main concept is to fix one character and recursively generate permutations for the remaining characters.
Python Code
def generate_permutations(s):
"""
Generate all permutations of a given string.
Parameters:
s (str): The string for which permutations are to be generated.
Returns:
list: A list of all permutations of the input string.
"""
def permute(s, l, r, result):
"""
Recursive helper function to generate permutations.
Parameters:
s (str): The string to permute.
l (int): The starting index of the string.
r (int): The ending index of the string.
result (list): The list to store all permutations.
"""
if l == r:
result.append(''.join(s))
else:
for i in range(l, r + 1):
s[l], s[i] = s[i], s[l] # Swap
permute(s, l + 1, r, result) # Recur
s[l], s[i] = s[i], s[l] # Swap back (backtrack)
result = []
s = list(s) # Convert string to list for in-place swapping
permute(s, 0, len(s) - 1, result)
return result
# Example usage
input_string = "abc"
permutations = generate_permutations(input_string)
print("Permutations of '{}' are: {}".format(input_string, permutations))
How the Program Works
- The
generate_permutations
function takes a strings
and initializes a listresult
to store the permutations. - The string is converted to a list of characters to facilitate in-place swapping.
- The
permute
function is a recursive helper function that generates permutations by swapping characters. It takes parameters for the string, start indexl
, end indexr
, and theresult
list. - When the start index equals the end index, a permutation is added to the
result
list. - The function swaps each character at index
l
with characters from indexl
tor
, recursively generates permutations for the remaining characters, and then swaps the characters back (backtracking). - Finally, the
result
list containing all permutations is returned.
Example Output
For the input string "abc"
, the output will be:
Permutations of 'abc' are: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']