An Iterator that generates all permutations of a string without keeping them in memory.

StringPermuter.java

import java.util.*;

/**
 * An Iterator that generates all permutations of a particular string, but
 * does not need to store them in memory.
 *
 * Example usage:
 *
 * Iterator<String> iter = new StringPermuter("Shilad");
 * while (iter.hasNext()) {
 *     System.out.println("permutation is: " + iter.next());
 * }
 *
 * @author Shilad Sen
 */
public class StringPermuter implements Iterator<String> {

    /**
     * A Node in the tree of permutation possibilities.
     * A Node is represented by a prefix for a permutation, along with some letters
     * that have not yet been used.
     * A node is terminal (a full permutation) if all letters have been used.
     * Children are all possible one character extensions of the prefix by one of
     * the unused characters.
     */
    private static class Node {
        private String prefix;
        private String unused;

        public Node(String prefix, String unused) {
            this.prefix = prefix;
            this.unused = unused;
        }

        public boolean isTerminal() {
            return this.unused.isEmpty();
        }

        public List<Node> children() {
            List<Node> result = new ArrayList<Node>();
            for (int i = 0; i < unused.length(); i++) {
                result.add(new Node(prefix + unused.charAt(i),
                                     unused.substring(0, i) + unused.substring(i+1)));
            }
            return result;
        }
    }

    private Stack<Node> stack = new Stack<Node>();

    public StringPermuter(String letters) {
        stack.push(new Node("", letters));
    }

    public boolean hasNext() {
        advance();
        return !stack.isEmpty();
    }

    public String next() {
        advance();
        if (stack.isEmpty() || !stack.peek().isTerminal()) {
            throw new IllegalStateException();
        } else {
            return stack.pop().prefix;
        }
    }

    // runs the DFS until we get a complete word on the stack
    private void advance() {
        while (!stack.isEmpty() && !stack.peek().isTerminal()) {
            List<Node> children = stack.pop().children();
            Collections.reverse(children);
            for (Node child : children) {
                stack.push(child);
            }
        }
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }

}