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']
    

 

By Aditya Bhuyan

I work as a cloud specialist. In addition to being an architect and SRE specialist, I work as a cloud engineer and developer. I have assisted my clients in converting their antiquated programmes into contemporary microservices that operate on various cloud computing platforms such as AWS, GCP, Azure, or VMware Tanzu, as well as orchestration systems such as Docker Swarm or Kubernetes. For over twenty years, I have been employed in the IT sector as a Java developer, J2EE architect, scrum master, and instructor. I write about Cloud Native and Cloud often. Bangalore, India is where my family and I call home. I maintain my physical and mental fitness by doing a lot of yoga and meditation.

Leave a Reply

Your email address will not be published. Required fields are marked *

error

Enjoy this blog? Please spread the word :)