Explain Codes LogoExplain Codes Logo

Generating all permutations of a given string

java
performance
optimizations
recursion
Nikita BarsukovbyNikita Barsukov·Feb 8, 2025
TLDR

To generate all permutations of a string, utilize the power of recursion and string manipulation. The process involves swapping each character with others and recursively processing the remaining substring.

public static void permute(String s) { permutation("", s); } private static void permutation(String prefix, String s) { int length = s.length(); if (length == 0) System.out.println(prefix); else { for (int i = 0; i < length; i++) permutation(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, length)); } } // Usage: permute("ABC");

The method permute initiates the process, while permutation acts as the recursive engine, gradually building up the prefix as permutations take shape. The output consists of all permutations such as: ABC, ACB, BAC and so on.

Explaining the logic and optimizing the process

The snippet above succinctly generates permutations, but would benefit from performance optimizations for longer strings. Here we delve into the inner workings and enhancements of the algorithm.

Dissecting recursion

The basis of recursion lies in breaking down a complex puzzle into simpler, similar sub-puzzles. Here are the critical components of our recursive solution:

  • Prefix: The starting segment of the new permutation being formulated.
  • Remaining: The untouched characters not yet added to the prefix.
  • Base Case: When the remaining string is empty, the recursion ends. The prefix is then a full permutation ready to be printed.
  • Recursive Case: The recursive magic where the function beckons itself to explore further permutations.

Using data structures for efficiency

To prevent duplicates, use a HashSet or TreeSet to store permutations:

Set<String> getPermutations(String s) { Set<String> permutations = new HashSet<>(); permutation("", s, permutations); return permutations; } void permutation(String prefix, String s, Set<String> permutations) { int n = s.length(); // Here comes magic ✨‿✨ if (n == 0) permutations.add(prefix); else { for (int i = 0; i < n; i++) permutation(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1), permutations); } }

Gracefully managing edge cases

Checking for empty or null inputs before delving into permutations rules out unnecessary computation, making the code more robust:

public static Set<String> permute(String s) { if (s == null || s.isEmpty()) return Collections.emptySet(); return getPermutations(s); }

Reducing memory footprint

Due to the increased recursion depth for longer strings, there is a risk of stack overflow. An iterative approach or tail recursion optimization could help ward off this issue.

Creating efficient output

By using StringBuilder instead of manipulating strings (which are immutable in Java), we can improve performance and lower memory overhead:

void permutation(StringBuilder prefix, int toPermuteLength, Set<String> permutations) { if (toPermuteLength == 0) permutations.add(prefix.toString()); else { for (int i = 0; i < toPermuteLength; i++) { swap(prefix, i, toPermuteLength-1); // Deeper we go 🕳️ permutation(prefix, toPermuteLength-1, permutations); swap(prefix, i, toPermuteLength-1); // Backtracking. Oops! Wrong turn 🔄 } } }

Adding gourmet details: advanced techniques and caveats

Implementing Heap's algorithm

Heap's algorithm is an alternative approach for efficiently generating the permutations of any given number of objects (characters, in our case):

void heapPermutation(char[] a, int size, Set<String> permutations) { if (size == 1) permutations.add(new String(a)); for (int i = 0; i < size; i++) { heapPermutation(a, size - 1, permutations); if (size % 2 == 1) { swap(a, 0, size - 1); } else { // Swap till you drop! 💃🕺 swap(a, i, size - 1); } } }

Keeping string length in check

The total permutations for a string of length n equals n-factorial (n!). As n increases, performance becomes crucial. In enterprise applications, optimizing memory usage and runtime becomes paramount.

Libraries to the rescue

Apache Commons Collections and Guava library from Google provide Permutation Generators. These libraries are highly optimized for performance and have withstood rigorous testing.