Find All the Permutations of a String in Java

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". This guide will show you how to create a Java program that finds and displays all permutations of a given string.

Problem Statement

Create a Java program that:

• Takes a string as input.
• Finds and displays all the permutations of that string.

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

Java Program to Find All Permutations of a String

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

• Input: The program prompts the user to enter a string.
• Recursive Permutation Generation: The findPermutations method generates all permutations of the input string by using recursion. The base case is when the input string is empty, at which point the accumulated prefix (which is a permutation) is printed. In the recursive case, the method iterates over the string, removing one character at a time and recursing on the remaining string.
• Output: Each permutation is printed as it is generated.

Output Example

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

Example 3:

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

Example 4:

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

Conclusion

This Java program generates all permutations of a given string using a recursive approach. By systematically removing one character at a time and recursing on the remaining characters, the program effectively generates and displays all possible permutations. This method is elegant and powerful, making it a common choice for generating permutations in programming tasks.