Unscramble Letters in Java - Get all possible combinations of the letters

Learn unscramble letters in java - get all possible combinations of the letters with practical examples, diagrams, and best practices. Covers java, cpu-word, scramble development techniques with vi...
Tags:
Categories:

Unscramble Letters in Java: Generating All Possible Combinations (Permutations)

Hero image for Unscramble Letters in Java - Get all possible combinations of the letters

Learn how to write a Java program to generate all unique permutations of a given set of letters. This article covers recursive approaches and handling duplicates.

Generating all possible combinations (permutations) of a set of letters is a classic computer science problem with applications in word games, cryptography, and combinatorial optimization. In Java, this can be efficiently solved using recursion. This article will guide you through implementing a solution that not only finds all permutations but also handles cases where the input string might contain duplicate characters.

Understanding Permutations and Recursion

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 letters 'ABC' have six permutations: ABC, ACB, BAC, BCA, CAB, CBA. The number of permutations for a set of 'n' distinct items is n! (n factorial).

Recursion is a powerful technique where a function calls itself to solve smaller instances of the same problem. For permutations, the idea is to fix one character at a time and then recursively find permutations of the remaining characters. This process continues until no characters are left, at which point a complete permutation has been formed.

flowchart TD
    A[Start Permutation Generation]
    B{Is input string empty?}
    C[Add current prefix to results]
    D[Iterate through remaining characters]
    E[Choose a character]
    F[Form new prefix + remaining string]
    G[Recursive Call: Permute(new prefix, remaining string)]
    A --> B
    B -- Yes --> C
    B -- No --> D
    D --> E
    E --> F
    F --> G
    G --> D

Flowchart illustrating the recursive permutation generation process.

Implementing the Permutation Algorithm

The core of the permutation algorithm involves a recursive function that takes two arguments: a 'prefix' (the characters already chosen for the current permutation) and the 'remaining' characters. In each recursive step, we pick one character from the 'remaining' set, append it to the 'prefix', and then call the function again with the updated 'prefix' and the reduced 'remaining' set. The base case is when the 'remaining' set is empty, meaning a full permutation has been constructed.

import java.util.HashSet;
import java.util.Set;

public class LetterScrambler {

    public Set<String> generatePermutations(String str) {
        Set<String> permutations = new HashSet<>();
        if (str == null || str.length() == 0) {
            return permutations;
        }
        permuteRecursive("", str, permutations);
        return permutations;
    }

    private void permuteRecursive(String prefix, String remaining, Set<String> result) {
        if (remaining.length() == 0) {
            result.add(prefix);
            return;
        }

        for (int i = 0; i < remaining.length(); i++) {
            char charToPick = remaining.charAt(i);
            String newPrefix = prefix + charToPick;
            String newRemaining = remaining.substring(0, i) + remaining.substring(i + 1);
            permuteRecursive(newPrefix, newRemaining, result);
        }
    }

    public static void main(String[] args) {
        LetterScrambler scrambler = new LetterScrambler();
        String input1 = "ABC";
        System.out.println("Permutations for '" + input1 + "': " + scrambler.generatePermutations(input1));

        String input2 = "ABA";
        System.out.println("Permutations for '" + input2 + "': " + scrambler.generatePermutations(input2));
    }
}

Java code for generating all unique permutations of a string using recursion.

Handling Duplicates More Efficiently (Optional Optimization)

While HashSet effectively removes duplicate permutations from the final result, the recursive process might still generate them internally. For very long strings with many duplicates, this can be inefficient. A more optimized approach involves sorting the input string first and then skipping duplicate characters during the recursive calls. This prevents redundant recursive branches.

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class OptimizedLetterScrambler {

    public Set<String> generatePermutations(String str) {
        Set<String> permutations = new HashSet<>();
        if (str == null || str.length() == 0) {
            return permutations;
        }
        char[] chars = str.toCharArray();
        Arrays.sort(chars); // Sort to handle duplicates efficiently
        boolean[] used = new boolean[chars.length];
        permuteOptimized(chars, used, new StringBuilder(), permutations);
        return permutations;
    }

    private void permuteOptimized(char[] chars, boolean[] used, StringBuilder currentPermutation, Set<String> result) {
        if (currentPermutation.length() == chars.length) {
            result.add(currentPermutation.toString());
            return;
        }

        for (int i = 0; i < chars.length; i++) {
            if (used[i]) {
                continue;
            }
            // Skip duplicates: if current char is same as previous AND previous was not used
            if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) {
                continue;
            }

            used[i] = true;
            currentPermutation.append(chars[i]);
            permuteOptimized(chars, used, currentPermutation, result);
            currentPermutation.deleteCharAt(currentPermutation.length() - 1); // Backtrack
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        OptimizedLetterScrambler scrambler = new OptimizedLetterScrambler();
        String input1 = "ABC";
        System.out.println("Optimized Permutations for '" + input1 + "': " + scrambler.generatePermutations(input1));

        String input2 = "ABA";
        System.out.println("Optimized Permutations for '" + input2 + "': " + scrambler.generatePermutations(input2));

        String input3 = "AABB";
        System.out.println("Optimized Permutations for '" + input3 + "': " + scrambler.generatePermutations(input3));
    }
}

Optimized Java code for generating unique permutations, handling duplicates more efficiently.