Generate all permutations of a given string and print them.
- User
Generate all permutations of a given string and print them.
Assistant
Of course! Generating all permutations of a string is a classic computer science problem that is an excellent showcase for recursion and backtracking.
The Core Idea: Recursion and Backtracking
The most intuitive way to solve this is to think recursively. For a string like "ABC":
-
Fix the first character ('A') and find all permutations of the rest of the string ("BC").
- The permutations of "BC" are "BC" and "CB".
- Combine these with the fixed 'A': "ABC" and "ACB".
-
Fix the second character ('B') in the first position (by swapping it with 'A') and find all permutations of the rest ("AC").
- The permutations of "AC" are "AC" and "CA".
- Combine these with the fixed 'B': "BAC" and "BCA".
-
Fix the third character ('C') in the first position (by swapping it with 'A') and find all permutations of the rest ("AB").
- The permutations of "AB" are "AB" and "BA".
- Combine these with the fixed 'C': "CAB" and "CBA".
This process of "choosing" a character for a position, exploring the consequences, and then "un-choosing" it to explore other options is called backtracking.
Algorithm Steps
Let's define a function
permute(string, left_index, right_index):-
Base Case: If
left_indexis equal toright_index, it means we have considered every character for every position. We have a complete permutation, so we print the current state of the string. -
Recursive Step: Loop from
i = left_indextoright_index. In each iteration: a. Choose: Swap the character atleft_indexwith the character ati. This places a new character at the beginning of the substring we're currently considering. b. Recurse: Callpermute(string, left_index + 1, right_index)to generate all permutations for the rest of the string. c. Backtrack: Swap the characters back to their original positions. This is crucial. It undoes the choice made in step (a) so that the next iteration of the loop can choose a different character for theleft_indexposition.
Python Implementation
Python's strings are immutable, so it's easier to work with a list of characters.
def permute(char_list, left, right): """ Generates all permutations of a list of characters. :param char_list: The list of characters to permute. :param left: The starting index for the current permutation (the fixed part). :param right: The ending index for the current permutation. """ # Base case: if left and right pointers are the same, # we have a complete permutation. if left == right: print("".join(char_list)) else: # Loop through the characters from the left pointer to the end. for i in range(left, right + 1): # 1. Choose: Swap the character at the left index with the current char char_list[left], char_list[i] = char_list[i], char_list[left] # 2. Recurse: Generate permutations for the rest of the list permute(char_list, left + 1, right) # 3. Backtrack: Swap them back to explore other possibilities char_list[left], char_list[i] = char_list[i], char_list[left] # --- Main part of the script --- if __name__ == "__main__": input_string = "ABC" print(f"Permutations of '{input_string}':") n = len(input_string) # Convert string to a list of characters as strings are immutable char_list = list(input_string) permute(char_list, 0, n - 1)Output:
Permutations of 'ABC': ABC ACB BAC BCA CBA CAB
Java Implementation
In Java, we can convert the string to a
char[]array to perform the swaps.public class StringPermutations { /** * Generates and prints all permutations of a string. * @param str The string to permute. * @param left The starting index of the substring to be permuted. * @param right The ending index of the substring to be permuted. */ private static void permute(char[] str, int left, int right) { // Base case: If left and right pointers meet, a permutation is found. if (left == right) { System.out.println(String.valueOf(str)); } else { // Loop through the characters from the left pointer to the end. for (int i = left; i <= right; i++) { // 1. Choose: Swap the character at the left index with the current char. swap(str, left, i); // 2. Recurse: Generate permutations for the rest of the string. permute(str, left + 1, right); // 3. Backtrack: Swap them back to restore the original state for the next iteration. swap(str, left, i); } } } /** * Helper function to swap characters in a char array. */ private static void swap(char[] arr, int i, int j) { char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void main(String[] args) { String input = "ABC"; System.out.println("Permutations of '" + input + "':"); int n = input.length(); permute(input.toCharArray(), 0, n - 1); } }Output:
Permutations of 'ABC': ABC ACB BAC BCA CBA CAB
C++ Implementation
C++ provides
std::swapwhich makes the code very clean.#include <iostream> #include <string> #include <algorithm> // For std::swap /** * @brief Generates and prints all permutations of a string. * @param str The string to permute (passed by reference). * @param left The starting index for the current permutation. * @param right The ending index for the current permutation. */ void permute(std::string& str, int left, int right) { // Base case: If we've reached the end of the string, print the permutation. if (left == right) { std::cout << str << std::endl; } else { // Loop through the characters from the left index to the end. for (int i = left; i <= right; ++i) { // 1. Choose: Swap the character at the 'left' position with the current character 'i'. std::swap(str[left], str[i]); // 2. Recurse: Generate permutations for the rest of the string. permute(str, left + 1, right); // 3. Backtrack: Swap them back to revert the string to its previous state. std::swap(str[left], str[i]); } } } int main() { std::string input = "ABC"; std::cout << "Permutations of '" << input << "':" << std::endl; int n = input.length(); permute(input, 0, n - 1); return 0; }Output:
Permutations of 'ABC': ABC ACB BAC BCA CBA CABHandling Duplicate Characters
The above algorithms will produce duplicate permutations if the input string has repeated characters (e.g., "AAB").
Problem: For "AAB", swapping the first 'A' with the second 'A' results in the same string, but the algorithm treats them as distinct swaps, leading to redundant recursive calls and duplicate final permutations.
Solution: Before swapping, add a check to ensure you don't place the same character in the current position (
left) more than once within the same loop.Here is the modified Python code to handle duplicates:
def permute_unique(char_list, left, right): if left == right: print("".join(char_list)) else: # Keep track of characters used in the current position used_chars = set() for i in range(left, right + 1): # If the character has already been used in this position, skip it if char_list[i] in used_chars: continue # Add the character to our set of used characters for this position used_chars.add(char_list[i]) # Swap, Recurse, Backtrack (as before) char_list[left], char_list[i] = char_list[i], char_list[left] permute_unique(char_list, left + 1, right) char_list[left], char_list[i] = char_list[i], char_list[left] # --- Main part of the script --- if __name__ == "__main__": input_string = "AAB" print(f"Unique permutations of '{input_string}':") n = len(input_string) char_list = list(input_string) permute_unique(char_list, 0, n - 1)Output for "AAB":
Unique permutations of 'AAB': AAB ABA BAA-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.