Java 8 – Find All the Permutations of a String

Introduction

Finding all the permutations of a string is a common problem in computer science, particularly in the fields of algorithms and combinatorics. A permutation is an arrangement of all or part of a set of objects, with regard to the order of the arrangement. For example, the permutations of the string "ABC" are "ABC", "ACB", "BAC", "BCA", "CAB", and "CBA". Java 8 provides powerful tools to solve this problem efficiently. In this guide, we will explore how to create a Java program that generates all permutations of a given string using recursion and Java 8 Streams.

Problem Statement

The task is to create a Java program that:

• Accepts a string as input.
• Uses recursion to generate all possible permutations of the string.
• Outputs each permutation.

Example 1:

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

Example 2:

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

Solution Steps

1. Input String: Start with a string that can either be hardcoded or provided by the user.
2. Generate Permutations: Use a recursive function to generate all permutations of the string.
3. Collect and Display the Result: Store the permutations in a list and print them.

Java Program

Java 8 Program to Find All the Permutations of a String

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * Java 8 Program to Find All the Permutations of a String
 * Author: https://www.rameshfadatare.com/
 */
public class StringPermutations {

    public static void main(String[] args) {
        // Step 1: Take input string
        String input = "ABC";

        // Step 2: Find all permutations
        List<String> permutations = findPermutations(input);

        // Step 3: Display the result
        permutations.forEach(System.out::println);
    }

    // Method to find all permutations of a string
    public static List<String> findPermutations(String str) {
        if (str == null || str.length() == 0) {
            return List.of("");
        }

        List<String> permutations = new ArrayList<>();
        char firstChar = str.charAt(0);
        String remainingString = str.substring(1);

        List<String> words = findPermutations(remainingString);
        for (String word : words) {
            for (int i = 0; i <= word.length(); i++) {
                String permutation = word.substring(0, i) + firstChar + word.substring(i);
                permutations.add(permutation);
            }
        }
        return permutations.stream().distinct().collect(Collectors.toList());
    }
}

Explanation of the Program

• Input Handling: The program uses the string "ABC" as an example input. This can be modified to accept input from the user if required.

• Recursive Permutation Generation: The findPermutations method generates all permutations of the string by recursively placing the first character of the string in every possible position of each permutation of the remaining substring.

• Base Case: If the input string is empty (""), the function returns a list containing an empty string. This is the base case for the recursion.

• Combining Results: The permutations are generated by iterating through each possible position to insert the first character in each permutation of the remaining substring.

• Removing Duplicates: Although the program doesn’t create duplicate permutations with distinct inputs, the distinct() method is used to ensure that all permutations are unique in case of repeated characters.

• Output: The program prints all the permutations of the input string.

Output Example

Example 1:

Input: ABC
Output:
ABC
ACB
BAC
BCA
CAB
CBA

Example 2:

Input: AB
Output:
AB
BA

Advanced Considerations

1. Handling Duplicates: If the input string contains duplicate characters (e.g., "AAB"), the program will still generate all unique permutations because of the distinct() method used when collecting the results.

2. Performance Considerations: The recursive approach used in this program is straightforward and works well for strings of moderate length. However, the number of permutations grows factorially with the length of the string (n! for a string of length n), so the program may become inefficient for very long strings.

3. Alternative Approaches: For very large strings or when generating permutations in a different context, other algorithms (such as iterative or backtracking methods) might be more efficient.

Conclusion

This Java 8 program efficiently generates all permutations of a string using recursion. By leveraging recursion and the power of Java 8 Streams, the solution is both concise and powerful, making it suitable for various applications in algorithm design, combinatorial problems, and text manipulation. Whether you’re studying permutations in computer science or working on a specific problem requiring all possible arrangements of characters, this method provides a clear and effective approach to generating permutations in Java.