Java Permutation Generator: Partial and Full Strings

Given any string, how many different ways can its characters be arranged?

That question originally motivated me to write this small Java program. At first glance, it sounds simple. You take a few letters and list every possible ordering. But once you start working on it, you quickly see how fast the number of results grows and how important small design decisions become.

Partial and Full Permutations

Most basic permutation generators only produce results that match the length of the input. If you give them three characters, they return three-character results and nothing else.

This program takes a different approach. It generates all permutations from length 1 through n, where n is the length of the input string.

Example: Permutations of “abc”

If the input is:

abc

The program produces:

a, b, c
ab, ac, ba, bc, ca, cb
abc, acb, bac, bca, cab, cba

This includes:

• All single-character permutations.
• All two-character permutations.
• All three-character permutations.

Together, these form the complete set of partial and full permutations.

This is especially useful for word-based games where valid solutions are not always the same length. Being able to generate every possible option makes filtering much easier later.

Why Explore Permutations?

It is a common introductory computer science problem. Working through it helps reinforce key concepts such as recursion, performance trade-offs, and time complexity.

I originally wrote this code to see just how quickly things got out of hand as more characters were added. Even small inputs can produce thousands or millions of combinations. That makes permutation generation a useful way to understand growth rates and algorithmic limits.

From a more practical perspective, a permutation generator powers several of my puzzle solvers, including the Quartiles Solver, Wordle Solver, and Spelling Bee Solver. The general pattern is always the same: generate possible letter arrangements, apply game rules, and compare the remaining candidates to a dictionary file.

Common Problems with Basic Generators

Simple permutation algorithms often work well for small examples, but they tend to break down in more realistic situations.

Duplicate Characters

Consider this input:

aab

A basic generator may produce:

aab, aba, aab, aba, baa, baa

These repeated results waste time and memory and require extra filtering.

Performance Overhead

Many implementations rely heavily on string concatenation and substring operations. This creates large numbers of temporary objects and slows things down as the input grows.

Recursion Limits

Recursive solutions are elegant and easy to read, but deep recursion can lead to stack overflow errors with larger inputs.

These problems are easy to overlook in small demos, but they become very noticeable when you try to build real tools on top of them.

Iterative Permutation Generator

To avoid these issues, this implementation uses an iterative, stack-based approach with built-in duplicate handling.

Instead of relying on the call stack, the program keeps track of partial results explicitly. This makes its behavior more predictable and easier to control.

Key Design Ideas

• Sort input characters to group duplicates.
• Track which characters are already in use.
• Use a stack to manage partial results.
• Skip branches that would lead to repeated output.

These ideas keep the code efficient without making it overly complex.

Java Implementation

import java.util.*;

public class PermutationGenerator {

  private static class State {
    StringBuilder current;
    boolean[] used;

    State(StringBuilder current, boolean[] used) {
      this.current = current;
      this.used = used;
    }
  }

  public static List<String> generateAll(String input) {
    List<String> result = new ArrayList<>();

    if (input == null || input.isEmpty()) {
      return result;
    }

    // Sort to group duplicates
    char[] chars = input.toCharArray();
    Arrays.sort(chars);

    int n = chars.length;

    Deque<State> stack = new ArrayDeque<>();

    // Initial empty state
    stack.push(new State(new StringBuilder(), new boolean[n]));

    while (!stack.isEmpty()) {
      State state = stack.pop();

      StringBuilder current = state.current;
      boolean[] used = state.used;

      // Add every non-empty prefix (partial permutation)
      if (current.length() > 0) {
        result.add(current.toString());
      }

      // Stop at full length
      if (current.length() == n) {
        continue;
      }

      // Iterate backwards so smaller indexes are processed first
      for (int i = n - 1; i >= 0; i--) {
        if (used[i])
          continue;

        // Skip duplicates
        if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) {
          continue;
        }

        // Copy state
        StringBuilder next = new StringBuilder(current);
        next.append(chars[i]);

        boolean[] nextUsed = Arrays.copyOf(used, n);
        nextUsed[i] = true;

        stack.push(new State(next, nextUsed));
      }
    }

    return result;
  }

  public static void main(String[] args) {
    for (String s : args) {
      System.out.println("Permutations of: " + s);

      List<String> perms = generateAll(s);

      for (String p : perms) {
        System.out.println(p);
      }

      System.out.println();
    }
  }
}

Performance and Complexity

Permutation generation grows extremely quickly.

For a string of length n, the total number of partial and full permutations from length 1 through n is calculated using the following formula:

For example, with a three-letter string like abc, there are 15 total arrangements when you include single characters, pairs, and full strings.

As n increases, this number rises very quickly. This is why permutation generators are best used with careful filtering and clear limits.

Usage Example

Compile and run the program using the input “abc”:

javac PermutationGenerator.java
java PermutationGenerator abc

Sample output:

Permutations of: abc
a
ab
abc
ac
acb
b
ba
bac
bc
bca
c
ca
cab
cb
cba

Summary

This Java permutation generator produces both partial and full permutations while avoiding duplicate results and recursion limits. Used thoughtfully, it turns a classic programming exercise into a reliable building block for real projects.