Generate All Permutations of a String in Java

This document provides a Java program to generate all permutations of a given string. The program utilizes a recursive approach to generate permutations and demonstrates how to handle string manipulation effectively in Java.

Java Program

public class StringPermutations {
    
    /**
     * Generates all permutations of a given string.
     * @param str The input string.
     */
    public static void generatePermutations(String str) {
        generatePermutations("", str);
    }
    
    /**
     * Recursive method to generate permutations.
     * @param prefix The current prefix.
     * @param str The remaining string to be permuted.
     */
    private static void generatePermutations(String prefix, String str) {
        int length = str.length();
        
        if (length == 0) {
            System.out.println(prefix);
        } else {
            for (int i = 0; i < length; i++) {
                // Generate the remaining string
                String newPrefix = prefix + str.charAt(i);
                String remaining = str.substring(0, i) + str.substring(i + 1, length);
                
                // Recur with the new prefix and remaining string
                generatePermutations(newPrefix, remaining);
            }
        }
    }

    public static void main(String[] args) {
        String input = "ABC";
        System.out.println("Permutations of the string \"" + input + "\":");
        generatePermutations(input);
    }
}
    

Program Explanation

The Java program to generate all permutations of a string is structured as follows:

1. Class Definition: The class StringPermutations contains all the methods required to generate permutations.
2. Method: generatePermutations(String str):
   • This public method is the entry point for generating permutations.
   • It calls a private recursive method generatePermutations(String prefix, String str) with an empty prefix and the original string.
3. Method: generatePermutations(String prefix, String str):
   • This is a private recursive method that generates permutations of the string.
   • If the remaining string str is empty, the current prefix is printed as a complete permutation.
   • Otherwise, the method iterates over each character of the string, creating new permutations by appending each character to the prefix and recursively generating permutations for the remaining substring.
4. Method: main(String[] args):
   • This is the entry point of the program where execution starts.
   • A sample input string “ABC” is used, and the generatePermutations method is called to display all permutations.

Explanation of the Program:

1. Class Definition: The StringPermutations class encapsulates the functionality for generating permutations.
2. generatePermutations(String str): This is the public method to start the permutation generation process. It initializes the recursive process by calling a private method with an empty prefix and the original string.
3. generatePermutations(String prefix, String str): This private recursive method is the core of the permutation generation. It:
   • Checks if the remaining string is empty. If so, prints the current prefix as a complete permutation.
   • Iterates over each character in the string, constructing new permutations by appending the character to the prefix and recursively calling itself with the remaining string.
4. main(String[] args): The main method where the program execution begins. It demonstrates the permutation functionality using a sample string “ABC”.