A generator function that enumerates all finite balanced parentheses strings

generate-balanced-parentheses.es6

// memoizes ordinary functions
const memoized = (fn, keymaker = JSON.stringify) => {
  const lookupTable = new Map();

  return function (...args) {
    const key = keymaker.call(this, args);

    return lookupTable[key] || (lookupTable[key] = fn.apply(this, args));
  }
};

// take a fixed number of elements from an iterable
function * take (numberToTake, iterable) {
  const iterator = iterable[Symbol.iterator]();

  for (let i = 0; i < numberToTake; ++i) {
    const { done, value } = iterator.next();
    if (done) return;
    else yield value;
  }
}

// a memoized random-access function for generators (not iterables)
const at = (
  atCache =>
  (generator, i) => {
      const { iterator, array } =
            atCache.get(generator) || 
            atCache.set(generator, { iterator: generator(), array: [] }).get(generator);

      while (array.length <= i) {
        const { done, value } = iterator.next();

        if (done) break;
        array.push(value);
      }

      return array[i];
    }
  )(new Map());

// upTo and downTo are generators for ranges of integers
function * upTo (i = 0, limit = Infinity) {
  while (i <= limit) yield i++;
}

function * downTo (i, base = 0) {
  while (i >= base) yield i--;
}

// generate all the ways to choose k elements
// from the set {0, 1, ... n-1}
//
// e.g. choose(2,3) yields [0, 1], [0, 2], [1, 2]
function * choose (k, n) {
  if (k < 1 || n < 1) {
    yield [];
    return;
  }
  
  for (const i of upTo(0, n - k)) {
    for (let lessChoice of choose(k - 1, n - i - 1)) {
      yield [i].concat(lessChoice.map(x => x + i + 1));
    }
  }
}

// given a breadth, eumerates all the combinations of integers
// from 0 to infinity. can't simply count: take 
// `enumerableCombinations(3)`, we can't yield `[0, 0, 0],
// [0, 0, 1], [0, 0, 2], ..., [0, 0, Infinity], that never
// yields combinations like [1962, 6, 14].
//
// so instead, it performs a progressive product, yielding
// [0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0], [0, 1, 1], [1, 0, 1],
// [1, 1, 0], [1, 1, 1], [0, 0, 2], [0, 1, 2], [1, 0, 2], [1, 1, 2]...
function * enumerableCombinations (breadth, max = Infinity) {
  if (breadth < 1) return;
  if (max < 0) return;
  
  yield new Array(breadth).fill(0);

  for (const limit of upTo(1, max)) {
    for (const numberOfLessers of downTo(breadth - 1, 0)) {
      for (const lesserIndices of choose(numberOfLessers, breadth)) {
        for (const lesserCombination of enumerableCombinations(numberOfLessers, limit - 1)) {
          const v = new Array(breadth).fill(limit);
          
          lesserIndices.forEach(
            (lesserIndex, i) => v[lesserIndex] = lesserCombination[i]
          );
          
          yield v;
        }
      }
    }
    
    yield new Array(breadth).fill(limit);
  }
}

// a helper that allows us to memoize enumerableCombinations(breadth)
const enumerableCombinationsForBreadth =
  memoized(
    breadth => () => enumerableCombinations(breadth)
  );

// each row is the number of parentheses at the top level,
// and each column takes the enumerable combinations and uses them as indices against
// the memoized index of this same generator
function * balanced () {
  // degenerate
  yield '';
  
  // diagonalize
  for (const diagonal of upTo(1)) {
    for (const numTopLevelPairs of upTo(1, diagonal)) {
      const horizontal = diagonal - numTopLevelPairs;
      const balancedIndices = at(enumerableCombinationsForBreadth(numTopLevelPairs), horizontal)
      const subBalanceds = balancedIndices.map(
        i => at(balanced, i)
      );
      yield subBalanceds.map(sub => `(${sub})`).join('');
    }
  }
}

take(16, balanced())
  //=>
    ''
    '()'
    '(())'
    '()()'
    '((()))'
    '()(())'
    '()()()'
    '(()())'
    '(())()'
    '()()(())'
    '()()()()'
    '(((())))'
    '(())(())'
    '()(())()'
    '()()()(())'
    '()()()()()'