Как посчитать и случайно выбрать вариант из комбинаторного пространства без перебора

За многими функциями стоит пространство комбинаций, которое слишком велико, чтобы вывести его целиком: конфигурации продукта, генерация тест-входов, процедурные уровни, генераторы выражений. Мы столкнулись с этим на Generative Grammar Engine, где раз за разом возникали три вопроса. Ни один из них не должен требовать, чтобы сначала построили всё пространство:

сколько всего вариантов,
взять один случайный,
показать несколько разных.

Генеративная грамматика это компактный пример такого пространства, и именно с ним работает движок. Он поддерживает грамматики в духе Tracery: правило это список альтернатив, а #name# внутри альтернативы подставляет по имени другое правило.

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

У этой крошечной грамматики 3 × 2 = 6 вариантов. У настоящих счёт идёт на миллионы. Все три ответа получаются из одного рекурсивного прохода по структуре, поэтому он написан один раз и переиспользуется.

Грамматика как дерево

Каждая альтернатива один раз разбирается в маленькое дерево. Литерал это текст. Ссылка указывает на другое правило. Последовательность это элементы, идущие подряд. Само правило это альтернация его опций.

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

Каждый вопрос ниже это проход по этому дереву.

Счёт без перечисления

Число вариантов подчиняется двум правилам. Последовательность это умножение: у #greeting# #name# количество исходов равно числу greeting на число name. Альтернация складывает: у правила с тремя опциями количество исходов равно сумме их исходов. Литерал это единица, а ссылка это счёт правила, на которое она указывает.

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;
};

Два обстоятельства делают это устойчивым. Грамматики могут ссылаться рекурсивно, когда правило ссылается на себя напрямую или через цепочку, поэтому проход несёт глубину, которая падает на каждой ссылке и останавливается на нуле, и это ограничивает иначе бесконечные правила. А результаты мемоизируются по глубине и шаблону, и правило, на которое ссылаются в двадцати местах, считается один раз. Грамматика с миллиардом вариантов отдаёт своё количество исходов сразу, потому что для этого ничего не перечисляется.

Один случайный вариант, равномерно

Взять равномерно случайный вариант сложнее, чем кажется на первый взгляд. Очевидный вариант проходит по дереву и выбирает опцию каждого правила с равной вероятностью, и распределение выходит перекошенным: опция, которая разворачивается в тысячу строк, оказывается не вероятнее опции, которая разворачивается в одну. Частые варианты становятся редкими. Так и было в первой версии, и от неё пришлось отказаться.

Решение переиспользует уже готовый счётчик: каждая опция взвешивается числом строк, которое может породить, и выбор идёт пропорционально:

// 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];
}

Теперь каждая финальная строка равновероятна, а это и значит «случайный вариант». В движке есть оба режима: равная вероятность на каждый выбор для быстрого разнообразия и взвешенный для равномерной выборки по всему пространству.

Несколько разных вариантов

Запрос на десять уникальных результатов у грамматики, в которой их всего шесть, должен вернуть шесть, а не зациклиться. Количество исходов задаёт потолок, так что больше, чем существует, запрошено не будет:

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); }
}

Перечислить всё, но с тормозом

Когда пространство мало, движок перечисляет его целиком. Последовательность это декартово произведение: каждое разворачивание левой части соединяется с каждым разворачиванием правой. Ограничитель останавливает произведение, прежде чем большая грамматика исчерпает память:

// #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;
}, [""]);

Общий подход

Один рекурсивный проход отвечает на всё. Правила простые: последовательность умножает, альтернация складывает, а мемоизация по глубине не даёт повторяющимся правилам считаться дважды. Те же счёты затем ведут и равномерную случайную выборку, и ограниченный список уникальных.

Этот приём не ограничен грамматиками. У всего, что собрано из комбинирующихся выборов, те же две операции: последовательность частей умножается, набор опций складывается. Конфигурации продукта, комбинаторные тест-входы, процедурные генераторы, построители запросов: всё это можно так же посчитать, сэмплировать и перечислить. Правило простое: сначала счёт, а перечисление только когда без него никак.