Java Program to Find All the Permutations of a String

Introduction

Finding all the permutations of a string is a common problem in computer science, especially in the fields of algorithm design and combinatorics. A permutation of a string is a rearrangement of its characters into different sequences. This guide will walk you through writing a Java program that generates all possible permutations of a given string.

Problem Statement

Create a Java program that:

• Prompts the user to enter a string.
• Generates and displays all possible permutations of the string.

Example:

• Input: "ABC"
• Output:

  ABC
  ACB
  BAC
  BCA
  CAB
  CBA
  

Solution Steps

1. Read the String: Use the Scanner class to take the string as input from the user.
2. Generate Permutations: Use recursion to generate all permutations of the string.
3. Display the Permutations: Print each permutation as it is generated.

Java Program

// Java Program to Find All the Permutations of a String
// Author: https://www.rameshfadatare.com/

import java.util.Scanner;

public class StringPermutations {
    public static void main(String[] args) {
        // Step 1: Read the string from the user
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter a string: ");
        String input = scanner.nextLine();
        
        // Step 2: Generate and display all permutations
        System.out.println("All permutations of the string are:");
        generatePermutations(input, "");
    }
    
    // Recursive method to generate permutations
    public static void generatePermutations(String str, String prefix) {
        if (str.length() == 0) {
            System.out.println(prefix);
        } else {
            for (int i = 0; i < str.length(); i++) {
                char ch = str.charAt(i);
                String remaining = str.substring(0, i) + str.substring(i + 1);
                generatePermutations(remaining, prefix + ch);
            }
        }
    }
}

Explanation

Step 1: Read the String

• The Scanner class is used to read a string input from the user. The nextLine() method captures the entire line as a string.

Step 2: Generate and Display All Permutations

• The generatePermutations() method is a recursive function that generates all permutations of the given string.
• The base case is when the string is empty (str.length() == 0), at which point the current permutation (prefix) is printed.
• The function iterates through the string, taking each character in turn, and recursively generates permutations of the remaining characters.

How Recursion Works:

• For a string "ABC", the function first considers ‘A’ as the first character, and then recursively finds all permutations of "BC".
• After completing permutations starting with ‘A’, it moves to ‘B’ as the first character and finds permutations of "AC", and so on.

Output Example

Example:

Enter a string: ABC
All permutations of the string are:
ABC
ACB
BAC
BCA
CAB
CBA

Conclusion

This Java program demonstrates how to generate and display all permutations of a given string. It utilizes recursion, a fundamental programming concept, to explore all possible arrangements of the characters in the string. This exercise is valuable for understanding recursion and combinatorial problems in Java programming.