Demystifying String Permutations

Finding all the possible rearrangements of a set of letters (known as **permutations**) is a classic computer science puzzle. It is solved using an algorithmic strategy called **backtracking**, where the computer builds options one step at a time and "rewinds" to try other possibilities.

In this guide, we will translate this complex concept into simple, 10-year-old friendly terms and trace how the program executes step by step.

Illustration of letter cards swapping to find all permutations of a string

Real-World Analogy: Rearranging Letter Cards on a Table

Imagine you have three letter cards: [A], [B], and [C]. You want to write down every possible combination of these cards.

To do this systematically without forgetting any, you follow a simple strategy:

Fix the first card: Keep [A] at the front, and write down the two choices for the remaining slots: A-B-C and A-C-B.
Swap the first card: Swap [A] with [B] so [B] is at the front. Write down the layouts: B-A-C and B-C-A.
Reset (Backtrack): Before you try another card for the front, swap [B] and [A] back to their starting positions (A-B-C) so you don't lose track of your cards!
Swap the first card again: Swap [A] with [C] so [C] is at the front. Write down the layouts: C-B-A and C-A-B. Reset back to starting positions.

Walkthrough of the Main Method Scenario

Let's trace how the program executes step by step from the entry point:

Step 1: Starting the Permutations

The program enters the main method and calls the entry function with the input string "ABC":

printPermutations("ABC");

It converts the string into a character array `['A', 'B', 'C']` and calls the recursive helper starting at index 0.

Step 2: Recursive Swapping and Backtracking

The helper method `permute(chars, currentIndex)` begins its work:

Level 0 (currentIndex = 0): The loop starts. It swaps chars[0] with itself (keeping 'A' at front) and calls `permute(chars, 1)`.
Level 1 (currentIndex = 1): The loop starts at index 1. It swaps chars[1] with itself (keeping 'B' second) and calls `permute(chars, 2)`.
Level 2 (Base Case, currentIndex = 2): Since `currentIndex` equals `chars.length - 1`, we print the current arrangement: ABC, and return (rewind).
Level 1 Swaps: It swaps chars[1] and chars[2] ('B' and 'C'), calls `permute(chars, 2)`, prints ACB, and returns. It then backtracks by swapping 'B' and 'C' back.
Level 0 Swaps: We return to Level 0. It swaps chars[0] and chars[1] ('A' and 'B'), calls `permute` to discover BAC and BCA, and backtracks. Finally, it swaps chars[0] and chars[2] ('A' and 'C') to find CBA and CAB.

Java Implementation

Below is the complete Java code showing the recursive swap and backtrack structure to generate permutations:

package io.practise.accolite;

public class PermutationOfString {

    public static void printPermutations(String str) {
        if (str == null || str.isEmpty()) {
            return;
        }
        permute(str.toCharArray(), 0);
    }

    private static void permute(char[] chars, int currentIndex) {
        // Base case: If we've reached the end of the string, we have a complete permutation.
        if (currentIndex == chars.length - 1) {
            System.out.println(new String(chars));
            return;
        }

        // Recursive step:
        for (int i = currentIndex; i < chars.length; i++) {
            // 1. Swap the character at the current index with the character at index 'i'.
            swap(chars, currentIndex, i);

            // 2. Recurse for the rest of the string (from the next index).
            permute(chars, currentIndex + 1);

            // 3. Backtrack: Swap the characters back to their original positions.
            swap(chars, currentIndex, i);
        }
    }

    private static void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }

    public static void main(String[] args) {
        String input = "ABC";
        System.out.println("Permutations for \"" + input + "\":");
        printPermutations(input);

        System.out.println("\nPermutations for \"GOD\":");
        printPermutations("GOD");
    }
}

Conclusion

Backtracking is a powerful algorithm pattern for exploring search spaces. By systematically swapping characters to explore combinations and immediately resetting (backtracking) them back, we generate all permutations cleanly and efficiently without needing extra memory grids.