1. Introduction

In computer science, a permutation of a set is, loosely speaking, an arrangement or rearrangement of its members into a sequence or linear order. In this tutorial, we will learn how to find all the permutations of a string in Java.

2. Program Steps

1. Define a main method to serve as the entry point of our program.

2. Define a string whose permutations we want to find.

3. Call the printPermutations function, passing the string and the start index as parameters.

The printPermutations function:

a) If the current index is the last index, print the permutation.

b) Otherwise, for each character in the string, swap the current index with the loop index and recursively call printPermutations.

c) After each recursive call, backtrack by swapping the characters back.

3. Code Program

public class StringPermutations {

    public static void main(String[] args) {
        // Step 2: Define a string
        String str = "ABC";
        // Step 3: Call the printPermutations function
        printPermutations(str, 0, str.length() - 1);
    }

    public static void printPermutations(String str, int l, int r) {
        if (l == r) // Step 3a: If the current index is the last index, print the permutation
            System.out.println(str);
        else {
            for (int i = l; i <= r; i++) {
                // Step 3b: Swap the current index with the loop index
                str = swap(str, l, i);
                // Recursive call to printPermutations with the next index
                printPermutations(str, l + 1, r);
                // Step 3c: Backtrack by swapping the characters back
                str = swap(str, l, i);
            }
        }
    }

    public static String swap(String a, int i, int j) {
        char temp;
        char[] charArray = a.toCharArray();
        temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
        return String.valueOf(charArray);
    }
}

Output:

ABC
ACB
BAC
BCA
CBA
CAB

4. Step By Step Explanation

– Step 1: The main method is defined, serving as the entry point of the program.

– Step 2: We define the string str whose permutations we want to find.

– Step 3: We call the printPermutations function with the string, start index, and end index.

a) If the current index is the last index, we print the permutation.b) We swap each character with the current index and make a recursive call to printPermutations.c) After the recursive call, we swap the characters back to their original positions (backtracking).

– swap Method: This helper method is used for swapping characters at positions i and j in a string.

The program prints all the permutations of the given string in the output.