Java Permutation Generator: Partial and Full Strings

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

That question was the original motivation for this small Java program. At first glance, it sounds simple: take a few letters and list every possible ordering. But the number of results grows fast, and small design decisions quickly become important.

Partial and Full Permutations

Most basic permutation generators only produce results that match the length of the input. Given 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 the following results, grouped here by length for clarity:

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.

This code was originally written 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, permutation generation can be useful in puzzle-solving programs. On this website, related techniques are used by several 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.

Stack Usage

Recursive solutions are elegant and easy to read, but each recursive call consumes stack space. With sufficiently large inputs, this can result in StackOverflowError.

These problems are easy to overlook in small demos, but they become very noticeable in real tools built 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 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$ containing distinct characters, 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, including single characters, pairs, and full strings. When the input contains duplicate characters, the number of unique permutations is lower because repeated arrangements are omitted.

As $n$ increases, this number rises very quickly. Because the program stores every generated permutation in a List, memory usage also grows with the number and total length of the generated strings. This is why permutation generators are best used with careful filtering and clear limits.

Usage

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

This implementation operates on Java char values, so it is intended for strings whose characters can be represented by individual UTF-16 code units.

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.