Counting and sampling a combinatorial space without enumerating it

Plenty of features hide a space of combinations too large to write out: product configurations, generated test inputs, procedural levels, expression generators. We ran into this while building Generative Grammar Engine, where three questions kept coming up. None of them should need the whole space built first:

how many possibilities exist,
draw a random one,
list a few distinct ones.

A generative grammar is a compact example of such a space, and it is what the engine works with. It runs Tracery-style grammars: a rule is a list of alternatives, and #name# inside an alternative pulls in another rule by name.

origin:   ["#greeting#, #name#"]
greeting: ["hello", "hi", "hey"]
name:     ["world", "friend"]

That tiny grammar has 3 × 2 = 6 outputs. Real ones reach into the millions. All three answers fall out of a single recursive walk over the structure, so that walk is written once and reused.

The grammar as a tree

Each alternative is parsed once into a small tree. A literal is text. A reference points at another rule. A sequence is parts in a row. A rule itself is an alternation of its options.

type AstNode =
  | { kind: "literal"; text: string }
  | { kind: "reference"; name: string }
  | { kind: "sequence"; parts: AstNode[] }
  | { kind: "alternation"; options: AstNode[] };

Every question below is a walk over this tree.

Counting without listing

The output count follows two rules. A sequence multiplies: #greeting# #name# has greeting-count times name-count. An alternation adds: a rule with three options has the sum of their counts. A literal is one, and a reference is the count of the rule it names.

const count = (node, depth) => {
  if (depth < 0) return 0;
  const k = `${depth}|${renderPattern(node)}`;
  if (memo.has(k)) return memo.get(k);

  let total;
  switch (node.kind) {
    case "literal":     total = 1; break;
    case "reference":   total = count(ruleAst[node.name], depth - 1); break;
    case "sequence":    total = node.parts.reduce((p, c) => p * count(c, depth), 1); break;
    case "alternation": total = node.options.reduce((s, o) => s + count(o, depth), 0); break;
  }
  memo.set(k, total);
  return total;
};

Two details make it hold up. Grammars can recurse, with a rule referencing itself directly or through a chain, so the walk carries a depth that drops on each reference and stops at zero, which bounds otherwise infinite rules. And results are memoized by depth and pattern, so a rule referenced in twenty places is counted once. A grammar with a billion outputs returns its total at once, because nothing is enumerated to get there.

One at random, evenly

Drawing a uniformly random output is harder than it first looks. The obvious version walks the tree and picks each rule’s option with equal probability, and the distribution comes out skewed: an option that expands into a thousand strings is no more likely than one that expands into a single string. Common outputs turn rare. That was the first attempt here, and it had to go.

The fix reuses the counter already built. Each option is weighted by how many strings it can produce, then picked proportionally:

// each option's chance is proportional to how many strings it can produce
const weights = alt.options.map((o) => count(o, depth));
const total = weights.reduce((a, b) => a + b, 0);
let pick = Math.floor(rng() * total);
let chosen = alt.options[0];
for (let i = 0; i < alt.options.length; i++) {
  if (pick < weights[i]) { chosen = alt.options[i]; break; }
  pick -= weights[i];
}

Now every final string is equally likely, which is what a random output should mean. The engine keeps both modes: equal-per-choice for quick variety, and weighted for an even draw across the whole space.

A few distinct outputs

Asking for ten unique results from a grammar that has only six should return six, not loop forever. The count gives the ceiling, so nothing asks for more than exist:

const limit = countStrings(start);              // never ask for more than exist
while (results.length < Math.min(n, limit)) {
  const g = generate(start);
  if (!seen.has(g.text)) { seen.add(g.text); results.push(g); }
}

Listing everything, with a brake

When the space is small, the engine enumerates it. A sequence is a cartesian product: every expansion of the left part joined with every expansion of the right. A cap stops the product before a large grammar exhausts memory:

// #A# #B# = every A combined with every B
node.parts.reduce((acc, part) => {
  const right = expandNode(part, d);
  const merged = [];
  for (const left of acc) for (const r of right) {
    merged.push(left.text + r.text);
    if (merged.length >= cap) return merged;   // stop before it explodes
  }
  return merged;
}, [""]);

The pattern

One recursive walk answers all of it. The rules are small: a sequence multiplies, an alternation adds, and memoization by depth keeps repeated rules from being counted twice. The same counts then drive an even random draw and a bounded unique list.

The shape generalizes past grammars. Anything built from choices that combine has the same two operations: a sequence of parts multiplies, a set of options adds. Product configurations, combinatorial test inputs, procedural generators, query builders, all of them can be counted, sampled, and listed the same way. The rule of thumb: count first, enumerate only when there is no way around it.