How to Find All Permutations of a String in Python

In this tutorial, we will learn about find all permutations of a string in Python. Permutations, commonly associated with mathematics, hold significance in computer science as well. Despite the perception that permutations are exclusively a mathematical topic, they find practical applications in various computational scenarios.

The field of mathematics in computer science serves a crucial purpose by imparting abstract communication skills, algorithmic problem-solving techniques, self-analysis of computational thought processes, and accurate representation of real-world solutions. There are many approaches available for finding all permutations of a string in Python, But before that let us understand what is string Permutation…

What is String Permutation?

A string permutation is an arrangement of its characters in a particular order. A new string is created by rearranging the characters of the old string. The number of permutations of a string depends on its length and is determined by the factorial of that length. Permutations are frequently employed in algorithms and tasks such as creating all possible combinations, solving riddles, and analyzing various element arrangements.

Different Approaches to find all Permutations of a String in Python

By using Recursive Approach
By using the Iterative Approach
By using itertools Approach

1. By using Recursive Approach

The recursive approach for finding all permutations of a string in Python refers to a technique where the problem is divided into smaller subproblems and a function is called recursively to solve each subproblem until a base case is reached. In the context of finding permutations, the recursive approach involves breaking down the problem of generating all permutations of a string into smaller subproblems by removing one character at a time and recursively finding permutations of the remaining characters

Algorithm:

Define a recursive function, let’s call it find_permutations(string), that takes a string as input.
If the length of the string is 1, return a list containing the string as a single permutation.
Otherwise, initialize an empty list, permutations, to store all permutations.
Iterate over each character, current_char, in the string.
Generate permutations of the remaining characters by recursively calling find_permutations on the substring obtained by removing current_char from the string.
Iterate over each permutation, sub_permutation, in the permutations obtained from the recursive call.
Append current_char to sub_permutation and add the resulting permutation to the permutations list.
Return the permutations list.

Example:

def find_permutations(string):
    # Base case: If the string has only one character, return it as a single permutation
    if len(string) == 1:
        return [string]

    # List to store all permutations
    permutations = []

    # Iterate over each character in the string
    for i in range(len(string)):
        # Extract the current character
        current_char = string[i]

        # Generate permutations of the remaining characters
        remaining_chars = string[:i] + string[i+1:]
        sub_permutations = find_permutations(remaining_chars)

        # Append the current character to each permutation of the remaining characters
        for sub_permutation in sub_permutations:
            permutations.append(current_char + sub_permutation)

    return permutations

# Example usage
input_string = "abc"
permutations_list = find_permutations(input_string)
print("The permutations of the string '{}' are:".format(input_string))
for perm in permutations_list:
    print(perm)

Output:

The permutations of the string 'abc' are:
abc
acb
bac
bca
cab
cba

In this program, the find_permutations function takes a string as input and recursively generates all possible permutations of the characters in the string.

The base case is when the string has only one character. In this case, there is only one permutation, so we return the string as a single-element list.

For strings with more than one character, we iterate over each character. For each character, we recursively generate permutations of the remaining characters by calling the find_permutations function. We remove the current character from the string and pass the remaining characters to the recursive call.

Then, we append the current character to each permutation of the remaining characters and store the resulting permutations in the permutations list.

Finally, we return the list of permutations.

Complexities:

Time Complexity: The time complexity of this recursive approach is O(n!), where n is the length of the input string. This is because there are n! possible permutations of a string of length n, and each permutation requires O(n) time to create.
Space Complexity: The space complexity is also O(n!), as there are n! permutations in the output list. Additionally, for each recursive call, a new substring is created, which contributes to the space complexity. The maximum depth of the recursion is n, so the space complexity is O(n) for the recursive call stack.

2. By using the Iterative Approach

The iterative approach for finding all permutations of a string in Python involves using a loop-based algorithm to generate permutations. Instead of relying on recursion, this approach iteratively constructs permutations by systematically generating and updating the permutations at each step. This iterative approach generates permutations by gradually building them up, adding one character at a time to existing permutations. By inserting the character at each possible position, it ensures that all valid permutations are generated.

Algorithm:

Initialize a list, permutations, with the input string as the initial permutation.
For each position from 0 to the length of the string minus 1:
- Create an empty list, new_permutations, to store the updated permutations.
- For each permutation in the current permutations list:
  - Insert the character at the current position into all possible positions of the permutation.
  - Add each updated permutation to the new_permutations list.
- Update the permutations list with the contents of new_permutations.
Return the permutations list as the result.

Example:

def find_permutations(string):
    permutations = [string]
    
    for i in range(len(string)):
        for perm in permutations[:]:
            chars = list(perm)
            for j in range(i+1, len(perm)):
                chars[i], chars[j] = chars[j], chars[i]
                new_perm = ''.join(chars)
                permutations.append(new_perm)
    
    return permutations

# Example usage
input_string = "abc"
permutations_list = find_permutations(input_string)
print("The permutations of the string '{}' are:".format(input_string))
for perm in permutations_list:
    print(perm)

Output:

The permutations of the string 'abc' are:
abc
bac
bca
acb
cab
cba

In this program, we define a function called find_permutations that takes a string as input. We start by creating a list called permutations and initializing it with the input string itself, as the first permutation.

We then iterate over each character of the string using the outer loop. For each character, we iterate over the existing permutations using the inner loop. We create a list of characters for the current permutation and swap the character at index “i” with each subsequent character from index i+1 onwards.

By doing this, we generate new permutations by swapping characters and append them to the permutations list.

Finally, we return the list of permutations.

Complexities:

Time complexity: The time complexity of this approach is O(n!), where n is the length of the input string. This is because there are n! permutations of an n-character string, and we need to generate all of them.
Space complexity: The space complexity is O(n!), as we need to store all the permutations in the permutations list. Each permutation has a length of n, resulting in n! permutations and consuming O(n!) space.

3. By using itertools Approach

The itertools approach for finding all permutations of a string in Python utilizes the permutations function from the itertools module. This approach provides a convenient and efficient way to generate permutations without explicitly implementing the permutation logic.

The permutations function takes an iterable, such as a string or a list, as input and returns an iterator that generates all possible permutations of the elements. Each permutation is represented as a tuple.

Algorithm:

Import the permutations function from the itertools module.
Define a function called find_permutations that takes a string as input.
Convert the input string into a list of characters.
Find all permutations of the characters using the permutations function.
Convert each permutation (represented as a tuple of characters) back into a string by joining them together.
Store the permutation strings in a list.
Return the list of permutation strings.

Example:

from itertools import permutations

def find_all_permutations(string):
    # Convert the string into a list of characters
    characters = list(string)
    
    # Find all permutations of the characters
    permuted_chars = permutations(characters)
    
    # Convert each permutation back into a string
    permutation_strings = [''.join(perm) for perm in permuted_chars]
    
    return permutation_strings

# Prompt the user to enter a string
input_string = "Developerhelps"

# Call the function to find all permutations
permutations_list = find_all_permutations(input_string)

# Print the permutations
print("The permutations of the string '{}' are:".format(input_string))
for perm in permutations_list:
    print(perm)

Output:

Enter a string: abc
The permutations of the string 'abc' are:
abc
acb
bac
bca
cab
cba

In this program, we define a function called find_all_permutations that takes a string as input. We start by converting the input string into a list of characters. Then, using the permutations function from the itertools module, we generate all possible permutations of the characters.

Next, we convert each permutation, represented as a tuple of characters, back into a string by using the join method. These strings are stored in the permutation_strings list.

Finally, we return the list of permutation strings. In the example usage, we prompt the user to enter a string and call the find_all_permutations function to find all permutations. We then iterate over the permutations and print each one.

Complexities:

Time Complexity: The time complexity of finding all permutations of a string using the permutations function from itertools is O(n!) since it generates all possible permutations. The factorial arises from the number of unique permutations possible for a string of length n.
Space Complexity: The space complexity is O(n!) as well because we need to store all the generated permutations in memory. The number of permutations is directly proportional to n!, where n is the length of the string.

Fuel Your Passion for Coding: Dive into Our Other Posts