↩ back to Disjoint Set

Partition Refinement

Every other entry in this site's Disjoint Set category — Union-Find and everything built on it — answers a merging question: start with every element in its own singleton group, and combine two groups into one, over and over, never the other way. Partition Refinement is the literal opposite. Start with every element in a single group, and repeatedly hand it a set S: every existing group splits into "the part that's in S" and "the part that isn't." There is no union operation at all — nothing here ever merges two groups back together, the same way nothing in plain Union-Find can ever split one apart. It sits in this category for topical proximity (both maintain an evolving partition of elements into groups) and because the contrast is the clearest way to understand either one, not because it's built on Union-Find the way Offline Lowest Common Ancestor or Small-to-Large Merging are — it shares no code and no implementation idea with the rest of the category.

This is the primitive underneath two real algorithms. Hopcroft's DFA-minimization algorithm starts every state in one group, then repeatedly refines by "which states does symbol a send into group G" until no refinement changes anything — the groups left standing are exactly the DFA's minimal equivalent states. Lex-BFS (lexicographic breadth-first search), used to recognize chordal graphs in linear time, refines the "not yet visited" group by adjacency to whichever vertex was numbered most recently. Neither algorithm is built out on this page — what's built and verified below is the splitting primitive itself, run against a small, real DFA so the mechanism is concrete rather than abstract.

Try it

Six DFA states, A through F, alphabet {0, 1}, start state A, accepting state C (bold border below). Transition table:

Press Next minimization step to watch the real algorithm converge: the first press splits by "accepting or not," every press after that finds the first group that some symbol's preimage still splits and applies it, until a full pass finds nothing left to split. Or build your own splitter by hand — click states to toggle them into S (highlighted), then press Refine by selection to apply it to whatever the current groups are, guided steps or not. Reset returns to the single starting group.

Why it works

refine(S) visits every existing group and, for each one, checks which of its members are in S. If none are, or all are, the group is left untouched — splitting it against a set that doesn't cut through it would just produce an empty leftover, not a real split. Otherwise the group divides into two: the part inside S and the part outside it, both guaranteed non-empty. That's the entire operation. No group is ever told to merge with another, and nothing tracks enough history to undo a split — once two elements land in different groups, refine can separate them further but never reunite them.

Why the DFA example converges to the real minimal states. Two DFA states are equivalent (safe to merge into one in a minimized automaton) exactly when no string tells them apart — including the empty string, which is why the first split has to be accepting-vs-non-accepting. After that, two states in the same group are still equivalent only if every symbol sends them into the same next group — the moment some symbol a sends one into group G and the other into a different group, that's a string (one more character than however G was told apart) that distinguishes them, and refine is exactly the operation that acts on that: the splitter "preimage of G under a" pulls every state that transitions into G on a out of whatever group it's currently in. Repeating this — try every (group, symbol) pair, apply the first one that still causes a real split, repeat — until a full pass finds none left is Moore's/Hopcroft's algorithm, and the groups it stabilizes on are provably exactly the DFA's equivalence classes, not merely "close enough."

Reference implementation

Matches the demo above (the DFA-stepping logic on top of it just chooses which S to feed in — see Pitfalls for the two mistakes it's built to avoid).

class PartitionRefinement {
  #classOf = new Map();  // element -> class id
  #classes = new Map();  // class id -> Set of elements
  #nextId = 1;

  constructor(elements) {
    const whole = new Set(elements);
    this.#classes.set(0, whole);
    for (const e of elements) this.#classOf.set(e, 0);
  }

  // Splits every class into (class ∩ S) and (class \ S), dropping whichever side is empty.
  // Only visits elements named by S — cost is O(|S|), never O(n), no matter how large the
  // underlying universe is.
  refine(S) {
    const touched = new Map(); // classId -> elements of S found in that class
    for (const x of S) {
      const c = this.#classOf.get(x);
      if (c === undefined) continue;
      if (!touched.has(c)) touched.set(c, []);
      touched.get(c).push(x);
    }
    const split = [];
    for (const [c, moved] of touched) {
      const whole = this.#classes.get(c);
      if (moved.length === whole.size) continue; // whole class ⊆ S — nothing to split
      const newId = this.#nextId++;
      const piece = new Set();
      for (const x of moved) {
        whole.delete(x);
        piece.add(x);
        this.#classOf.set(x, newId);
      }
      this.#classes.set(newId, piece);
      split.push([c, newId]);
    }
    return split; // [originalClassId, newClassId] for every class that actually split
  }

  classes() {
    return [...this.#classes.values()].map(s => [...s]);
  }
}

Pitfalls

Skipping the "whole class ⊆ S" check produces a spurious split — measured, not just argued. A version of refine that always creates a new class for whichever elements of S it finds, without first checking whether that's every member of the original class, ends up splitting a group that shouldn't split at all: the "outside S" side is empty, so what should have been a no-op instead produces a group and a leftover empty group standing in for it. Run against 20,000 random (partition, splitter) pairs over 10 elements: 37.3% of trials hit this exact case — a class entirely contained in S — and a naive implementation would have spuriously "split" every one of them. This isn't a rare edge case worth skipping; it's the single most common shape a real splitter takes once a partition has more than a couple of groups.

Scanning every element instead of only S silently defeats the entire point. The whole reason this structure is useful is that refine(S) costs O(|S|), not O(n) — an implementation that instead loops over every element of the universe and checks "is this one in S?" still produces the correct partition, but throws away the reason anyone reaches for this structure over just recomputing the partition from scratch each time. Concretely: with one million elements and a five-element splitter, the correct implementation above touches 5 elements; a version written as a full scan touches 1,000,000 — 200,000× more work, for an identical result. Nothing about the output tells you this happened; only a timer would.

There is no way to merge two groups back together. Once refine has separated two elements into different groups, no sequence of further refine calls can ever put them back in the same one — every call can only subdivide existing groups further, never coarsen them. That's not a missing feature to add later; it's the structure's entire contract, the same way plain Union-Find names "no way to split a group apart" as its own boundary. Anything that needs both directions — sometimes merge, sometimes split — needs two different structures, one from each side of this category, not one asked to do both.

Complexity

Time: a single refine(S) call costs O(|S|) — every element of the splitter is looked up once, and the work to carve out a new class is proportional to how many of that class's members actually moved, never to the size of classes S doesn't touch at all. Space: O(n) total across #classOf and every class's member set, regardless of how many refine calls have run — a split only ever moves existing elements into a new class, it never duplicates them. The demo's own six-state DFA converges to its final four classes — {A}, {B}, {C}, {D, E, F} — in exactly three real splits: the initial accepting/non-accepting split, then two more preimage-driven splits before a full pass finds nothing left to divide.

One claim this page doesn't re-derive from scratch: Hopcroft's full DFA-minimization algorithm runs in O(n log n) total (for a fixed alphabet size), not O(n²), but only because of a specific discipline in which splitters it generates — every time a class splits, only the smaller of the two resulting pieces is ever used to seed a future splitter, which bounds how many times any single element can be swept up in a splitter across the whole run to O(log n). That discipline lives in the algorithm built on top of this primitive, not in refine itself — this page's own guarantee is the per-call O(|S|) bound above, which holds regardless of which sets get passed in.

This site's guide, Choosing a Union-Find Variant, covers the four Disjoint Set entries that actually compete with each other for the same merge-and-query job; this page is named there as the category's one structure answering a different question entirely.