Skip to content
TheChatArchiveThe Chat Archive
Geminigemini-2.5-pro· GoogleHugging Face LMArena Human Preference 140K

Generate all permutations of a given string and print them.

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Googlegemma-3n-e4b-it’s answer.
  1. User

    Generate all permutations of a given string and print them.

  2. Gemini 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":

    1. 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".
    2. 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".
    3. 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):

    1. Base Case: If left_index is equal to right_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.

    2. Recursive Step: Loop from i = left_index to right_index. In each iteration: a. Choose: Swap the character at left_index with the character at i. This places a new character at the beginning of the substring we're currently considering. b. Recurse: Call permute(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 the left_index position.


    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::swap which 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
    CAB
    

    Handling 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
    

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.