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

1. The generate_permutations function takes a string s and initializes a list result to store the permutations.
2. The string is converted to a list of characters to facilitate in-place swapping.
3. The permute function is a recursive helper function that generates permutations by swapping characters. It takes parameters for the string, start index l, end index r, and the result list.
4. When the start index equals the end index, a permutation is added to the result list.
5. The function swaps each character at index l with characters from index l to r, recursively generates permutations for the remaining characters, and then swaps the characters back (backtracking).
6. 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']