How to generate all permutations of a given string

Key takeaways:

  • Permutations rearrange string characters into all unique orders, like "car" → ["car", "cra", "acr", "arc", "rca", "rac"].

  • Recursion explores all combinations by breaking the problem into smaller sub-problems.

  • itertools.permutations() provides a quick, built-in way to generate permutations.

  • Both methods, recursion and itertools.permutations(), have a factorial time complexity, O(n!)O(n!), and high space usage, O(n×n!)O(n × n!).

Generating a string’s permutations involves rearranging the string’s characters to produce all possible unique arrangements. Each permutation represents a distinct order of the original characters, maintaining the same set of elements. For instance, the string “car” can be rearranged into six unique permutations, as shown below:

  • "car"

  • "cra"

  • "acr"

  • "arc"

  • "rca"

  • "rac"

Permutations are an important concept in combinatorics and have applications in problems like anagrams, sequencing, and combinatorial optimization. Using recursion or libraries like Python’s itertools, one can generate these permutations, exploring every possible arrangement.

A similar concept is generating combinations, where the focus is on selecting characters without considering their order, unlike permutations. For a deeper dive into how these two concepts are related, check out the article: How are permutations and combinations related to each other?.

Recursion

Recursion is a powerful programming technique where a function calls itself to tackle smaller instances of the same problem, gradually breaking down the complexity. By dividing the task into simpler sub-problems, recursion ensures that the solution moves step-by-step until reaching a defined base case that terminates the recursion.

Recursion selects a character from the input string, processes the remaining characters, and combines them to explore every possible arrangement. This approach ensures that all unique permutations are generated by dividing the problem into smaller subproblems and solving them recursively.

The following Python code snippet demonstrates how recursion can be implemented to compute all permutations of a given string:

def generate_permutations(string):
# Base case: If the string has one character, return it as the only permutation
if len(string) == 1:
return [string]
# List to store permutations
permutations = []
for i in range(len(string)):
# Fix the first character
first_character = string[i]
# Get the remaining characters
remaining_characters = string[:i] + string[i + 1:]
# Recursively generate permutations for the remaining characters
permutations_of_remaining_characters = generate_permutations(remaining_characters)
# Combine the fixed character with permutations of the remaining characters
for permutation in permutations_of_remaining_characters:
permutations.append(first_character + permutation)
# Return the list of permutations
return permutations
# Driver code
def main():
strings = ["care", "bad", "apple", "mat", "as"]
for i in range(len(strings)):
print(i + 1, ".\tString: \"" + strings[i] + "\"")
print("\tPermutations: ", generate_permutations(strings[i]))
print("-" * 100)
main()

Recursion works well for generating permutations, but it can quickly lead to a stack overflow if the string is too long. For safety, always consider the problem's complexity before computing!

Code explanation

  • Lines 3–4 (Base case): Return the input string in a list if it has only one character.

  • Line 7: Initialize an empty list to store permutations.

  • Lines 9–21: Iterate through each character, extracts it as first_character, and recursively generates permutations for the rest. Combines results and appends them to the list.

  • Line 24: Return the list of all permutations.

  • Lines 27–33: Define the main() function to generate and print permutations for multiple strings.

Time complexity

The time complexity of the generate_permutations() function is O(n!)O(n!), where nn is the length of the input string. The function explores all character positions in the string, leading to nn possibilities at the first level, n1n-1 at the second, and so on. This sequential reduction results in n(n1)...1n * (n-1) * ... * 1 possibilities, which is n!n!. Thus, the time complexity is O(n!)O(n!).

Space complexity

The space complexity of the generatePermutations() function is O(nn!)O(n * n!), where nn is the length of the input string. The recursion and list to store permutations contribute to this complexity, resulting in nn recursive calls and n!n! permutations generated, leading to exponential growth with the input string’s length.

itertools function

We can use the itertools library in Python to generate all permutations of a given string. The code snippet below shows how itertools can be used to generate all permutations of a given string.

import itertools
def generate_permutations(string):
# List to store the permutations
permutations = []
# Use itertools.permutations to generate all permutations of the string
for _, perm in enumerate(list(itertools.permutations(string))):
# Convert each tuple to a string and append
permutations.append(''.join(perm))
# Return the list of permutations
return permutations
# Driver code
def main():
strings = ["care", "bad", "apple", "mat", "as"]
for i in range(len(strings)):
print(i + 1, ".\tString: \"" + strings[i] + "\"")
print("\tPermutations: ", generate_permutations(strings[i]))
print("-" * 100)
main()

itertools.permutations() is like having a “magic wand” for permutations. It instantly generates all possible arrangements without writing complex code. However, be careful: for long strings, the number of permutations grows explosively (For example, a 10-character string has 3,628,800 permutations).

Code explanation

  • Line 1: Import the itertools library.

  • Line 6: Initialize an empty list for storing permutations.

  • Lines 9–12: Use itertools.permutations() to generate and append permutations to the list.

  • Line 15: Return the list of all permutations.

  • Lines 18–24: Define the main() function to generate and print permutations for multiple strings.

Time complexity

The time complexity of the itertools.permutations() function is O(nn!)O(n * n!), where nn is the length of the input string. This is because the method generates n!n! permutations, and for each permutation, the join() operation takes O(n)O(n) time.

Space complexity

There are n!n! permutations, each of the length nn. Hence the space complexity of the itertools.permutations() function is O(nn!)O(n * n!).

Frequently asked questions

Haven’t found what you were looking for? Contact Us


What is a permutation in the context of strings?

A permutation is a unique arrangement of the characters in a string, where the order of characters changes while keeping the same set of elements.


How does recursion generate permutations?

Recursion solves the problem by breaking it into smaller parts. It fixes one character at a time and generates permutations for the remaining characters, combining them to produce all possible arrangements.


How does itertools.permutations() simplify the process?

itertools.permutations() is a Python library function that directly generates all permutations of a string without manually implementing recursive logic.


Why is the space complexity high for permutation generation?

Both recursion and itertools store all permutations in memory, resulting in a space complexity of O(n×n!)O(n × n!), where nn is the string length. This includes memory for recursive calls and the output list.


Free Resources

Copyright ©2025 Educative, Inc. All rights reserved