Java Program to Find all Permutations of String

Introduction

A permutation of a string is a rearrangement of its characters. For example, the permutations of the string "ABC" are "ABC", "ACB", "BAC", "BCA", "CAB", and "CBA". In this guide, we will create a Java program to find and display all possible permutations of a given string.

Problem Statement

Create a Java program that:

• Takes a string as input.
• Finds all the permutations of that string.
• Displays each permutation.

Example 1:

• Input: "ABC"
• Output: ABC, ACB, BAC, BCA, CAB, CBA

Example 2:

• Input: "AB"
• Output: AB, BA

Solution Steps

1. Prompt for Input: Use the Scanner class to read a string input from the user.
2. Create a Recursive Method: Use a recursive method to generate all permutations of the string.
3. Display Each Permutation: Print each permutation as it is generated.

Java Program

import java.util.Scanner;

/**
 * Java Program to Find All Permutations of a String
 * Author: https://www.javaguides.net/
 */
public class StringPermutations {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Step 1: Prompt the user for input
        System.out.print("Enter a string to find its permutations: ");
        String input = scanner.nextLine();

        // Step 2: Generate and display permutations
        System.out.println("Permutations of the string are:");
        findPermutations(input, "");
    }

    // Step 3: Recursive method to find permutations
    public static void findPermutations(String str, String prefix) {
        if (str.isEmpty()) {
            // Base case: If the string is empty, print the prefix
            System.out.println(prefix);
        } else {
            for (int i = 0; i < str.length(); i++) {
                // Choose the character at index i
                char ch = str.charAt(i);

                // Form the remaining string after removing the character at index i
                String remaining = str.substring(0, i) + str.substring(i + 1);

                // Recurse with the remaining string and the prefix updated with the chosen character
                findPermutations(remaining, prefix + ch);
            }
        }
    }
}

Explanation

Step 1: Prompt for Input

• The program uses the Scanner class to read a string input from the user. This string will be used to generate permutations.

Step 2: Generate and Display Permutations

• The program calls the findPermutations method, passing the input string and an empty string as the initial prefix.

Step 3: Recursive Method to Find Permutations

• Base Case: If the string str is empty, the current permutation (held in prefix) is printed.
• Recursive Case:
  • The method loops through each character in the string.
  • For each character, it creates a new string by removing the current character from the original string.
  • The method then recursively calls itself with the new string (remaining) and the updated prefix (which includes the current character).

Key Points:

• The base case ensures that when the string becomes empty, the accumulated prefix (which is a complete permutation) is printed.
• The recursive case systematically explores all possible permutations by choosing each character in turn and recursing on the remaining characters.

Output Examples

Example 1:

Enter a string to find its permutations: ABC
Permutations of the string are:
ABC
ACB
BAC
BCA
CAB
CBA

Example 2:

Enter a string to find its permutations: AB
Permutations of the string are:
AB
BA

Conclusion

This Java program efficiently finds and displays all permutations of a given string using recursion. The recursive approach is well-suited for this task as it naturally breaks down the problem into smaller subproblems. This method is both elegant and powerful, making it a common choice for generating permutations in programming.