Work in Progress on Generating Balanced Parentheses

base.ts

export const Zero = 0;
export const One = 1;

export type NonnegativePair = [x: number, y: number];
export type NonnegativeTriplet = [...NonnegativePair, z: number];

export function * take<T>(n:  number, source: Generator<T>) {
  let i = 1;

  for (const element of source) {
    if (i++ > n) return;

    yield element;
  }
}

simple.test.ts

import { take } from "./base";
import { dyckWords, mapPositiveToNonnegativePair } from "./simple";

test("dyck words: simple 2d path", () => {
  const pathIn2d: number[][] = [
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
  ];
  
  for (let i = 1; i <= 25; i++) {
    const [x, y] = mapPositiveToNonnegativePair(i);

    (pathIn2d[x] || [])[y] = i;
  }

  expect(pathIn2d).toEqual([
    [ 1,  4,  5, 16, 17],
    [ 2,  3,  6, 15, 18],
    [ 9,  8,  7, 14, 19],
    [10, 11, 12, 13, 20],
    [25, 24, 23, 22, 21]
  ])
});

test("dyck words: simple words", () => {
  expect([...take(25, dyckWords('(', ')'))]).toEqual([
    "", "()", "(())", "(())()", "()()",
    "()(())", "(())(())", "((()))(())", "((()))()", "((()))",
    "((())())", "((())())()", "((())())(())", "((())())(())()", "((()))(())()",
    "(())(())()", "()(())()", "()()()", "(())()()", "((()))()()",
    "((())())()()", "(()())()()", "(()())(())()", "(()())(())", "(()())()"
  ])
});

simple.ts

/**
 *
 * Constructive demonstration that the simple (one type of parentheses)
 * balanced parentheses language can be placed into a 1:1 correspondence
 * with the integers, and then generated in sequence.
 *
 */

import { NonnegativePair, One, Zero } from "./base";

/**
 * 
 * Maps the positive integers (1..∞) to tuples of nonnegative integers (0..∞, 0..∞).
 * by diagonalizing them on a grid using the following path:
 * 
 *      |  0 |  1 |  2 |  3 |  …
 *      |----|----|----|----|---
 * |  0 |  1 |  4 |  5 | 16 | 17
 * |  1 |  2 |  3 |  6 | 15 | 18
 * |  2 |  9 |  8 |  7 | 14 | 19
 * |  3 | 10 | 11 | 12 | 13 | 20
 * |  … | 25 | 24 | 23 | 22 | 21…
 * 
 * Each cell represents a pair marked by the horizontal and vertical labels. For example,
 * square 11 has a vertical label of 3 and a horizontal label of 1.
 * 
 * @param positive a positive integer
 * @returns a tuple of nonnegative integers
 * 
 */
export function mapPositiveToNonnegativePair (positive: number): NonnegativePair {

  // erroneous inputs
  if (positive < One) throw new RangeError();
  if (positive != Math.floor(positive)) throw new RangeError();

  // base case
  if (positive === One) return [Zero, Zero];

  // positive numbers > 1
  //
  // We find the location of `positive` on the path in the above chart.

  // First, we compute the bounding square, which is the smallest square
  // that contains both `1` and `positive`. This is the length of
  // its side:
  
  const boundingSquareSideLength = Math.ceil(Math.sqrt(positive));

  // This value is important, as it is at least one
  // of the two integers in the pair: The index lies upon that
  // column, that row, or both.

  // Given index = 6, boundingSquareSideLength will be 3.
  //
  //      |  0 |  1 |  2 |  3 |  …
  //      |----|----|----|----|---
  // |  0 |    |    |  5 |    | 
  // |  1 |    |    |  6 |    | 
  // |  2 |  9 |  8 |  7 |    | 
  // |  3 |    |    |    |    | 
  // |  … |    |    |    |    | 
  // 
  // Compute the distance of the index along the track:

  const innerArea = Math.pow(boundingSquareSideLength - 1, 2);
  const distanceAlongOuterBoxSides = positive - innerArea;

  // Now for number fiddling to derive the pair from the indices
  // of the poaitive along the track.
  //
  // The numbers can run down and then left,
  // or right and then up, they alternate with each
  // row and column.
  //
  // Whichever way they start, the first half will be in ascending order
  // of rows or columns, up to and including the corner. The second
  // half will be descending order of rowns and colums.

  const isInFirstHalfOfTrack = distanceAlongOuterBoxSides <= boundingSquareSideLength;

  // now we can compute the indices of the index. We still don't know
  // which way the numbers run, but since it's symmetrical, we can sort
  // that out afterwards.

  const boundingBoxArea = Math.pow(boundingSquareSideLength, 2);
  const boundiingBoxColumnOrRowIndex = boundingSquareSideLength - 1;

  const indices: NonnegativePair =
    isInFirstHalfOfTrack
      ? [distanceAlongOuterBoxSides - 1, boundiingBoxColumnOrRowIndex]
      : [boundiingBoxColumnOrRowIndex, boundingBoxArea - positive];

  // Now we work out the direction:

  const downAndThenLeft = boundingSquareSideLength % 2 === 1;

  // And return the pair, oriented according to the direction needed.

  return downAndThenLeft
    ? indices
    : indices.toReversed() as NonnegativePair;
}

/**
 * 
 * Maps a positive number to a Dyck word by mapping that integer to a pair of nonnegatives,
 * which in turn map to empty or another pair and so on down to `1`, the base case.
 * The basis of the mapping is XxYy where X and Y are the symbols in a simple Dyck language,
 * and x and y are either empty or another valid word in the Dyck language.
 * 
 * We use the diagonalization path:
 * 
 *      |  0 |  1 |  2 |  3 |  …
 *      |----|----|----|----|---
 * |  0 |  1 |  4 |  5 | 16 | 17
 * |  1 |  2 |  3 |  6 | 15 | 18
 * |  2 |  9 |  8 |  7 | 14 | 19
 * |  3 | 10 | 11 | 12 | 13 | 20
 * |  … | 25 | 24 | 23 | 22 | 21
 * 
 * The row and column indices now map to the "parent" dyck words. In the case of balanced parentheses:
 * 
 *          |        | ()       | (())       |
 *          |--------|----------|----------- |
 * |        | ()     | ()()     | ()(())     |
 * | ()     | (())   | (())()   | (())(())   |
 * | (())   | ((())) | ((()))() | ((()))(()) |
 *
 * @param X the first symbol of the pair
 * @param Y the second symbol of the pair
 * @param nonnegative a positive or counting number 
 * @returns a string
 */
export function mapNonnegativeToDyckWord(X: string, Y: string, nonnegative: number): string {

  // See mapPositiveToNonnegativePair for general comments about the agorithm for determening the x and y coördinates

  // erroneous inputs
  if (nonnegative < Zero) throw new RangeError();
  if (nonnegative != Math.floor(nonnegative)) throw new RangeError();

  // degenerate case
  if (nonnegative === 0) return '';

  // recursive case
  const [x, y] = mapPositiveToNonnegativePair(nonnegative);

  return `${X}${mapNonnegativeToDyckWord(X, Y, x)}${Y}${mapNonnegativeToDyckWord(X, Y, y)}`;
}

export function * dyckWords(X: string, Y: string) {
  let n = 0;

  while (true) {
    yield mapNonnegativeToDyckWord(X, Y, n++);
  }
}

typed.test.ts

/**
 *
 * Constructive demonstration that any (with one or more types)
 * balanced parentheses language can be placed into a 1:1 correspondence
 * with the integers, and then generated in sequence.
 * 
 * We will work along the same lines as the simple balanced parentheses,
 * but introduce a third integer to represent the type of parentheses.
 *
 */

import { NonnegativeTriplet, take } from "./base";
import { mapPositiveToNonnegativeTriplet, typedDyckWords } from "./typed";

test("dyck words: path in 3d", () => {
  const pathIn3d: NonnegativeTriplet[][] = [
    [[0, 0, 0], [0, 0, 0], [0, 0, 0]],
    [[0, 0, 0], [0, 0, 0], [0, 0, 0]],
    [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
  ];
  
  for (let i = 1; i <= 27; i++) {
    const [x, y, z] = mapPositiveToNonnegativeTriplet(i, 3);

    ((pathIn3d[x] || [])[y] || [])[z] = i;
  }

  expect(pathIn3d).toEqual([
    [[ 1,  2,  3], [10, 11, 12], [13, 14, 15]],
    [[ 4,  5,  6], [ 7,  8,  9], [16, 17, 18]],
    [[25, 26, 27], [22, 23, 24], [19, 20, 21]]
  ])
});

/**
 * 
 * The generate case for the 3d path is where there\
 * is only one level. If all is correct, it will behave
 * very much like our simple map above, albeit with
 * a slightly different data structure.
 */
test("dyck words: degenerate path in 3d", () => {
  const pathIn3d: number[][][] = [
    [[0], [0], [0]],
    [[0], [0], [0]],
    [[0], [0], [0]]
  ];
  
  for (let i = 1; i <= 9; i++) {
    const [x, y, z] = mapPositiveToNonnegativeTriplet(i, 1);

    ((pathIn3d[x] || [])[y] || [])[z] = i;
  }

  expect(pathIn3d).toEqual([
    [[1], [4], [5]],
    [[2], [3], [6]],
    [[9], [8], [7]]
  ])
});

test("dyck words: typed words", () => {
  // the degenerate case, one pair of symbols
  expect([...take(25, typedDyckWords('(', ')'))]).toEqual([
    "", "()", "(())", "(())()", "()()",
    "()(())", "(())(())", "((()))(())", "((()))()", "((()))",
    "((())())", "((())())()", "((())())(())", "((())())(())()", "((()))(())()",
    "(())(())()", "()(())()", "()()()", "(())()()", "((()))()()",
    "((())())()()", "(()())()()", "(()())(())()", "(()())(())", "(()())()"
  ]);

  // the first four as a sanity check, zero and the first three in position 1.
  expect([...take(4, typedDyckWords('(', ')', '[', ']', '{', '}'))]).toEqual([
    "", // the degenerate case
    "()",
    "[]",
    "{}"
  ]);
  expect([...take(19, typedDyckWords('(', ')', '[', ']', '{', '}'))]).toEqual([
    "", // the degenerate case
    "()", "[]", "{}",
    "(())", "[()]", "{()}",
    "(())()", "[()]()", "{()}()",
    "()()", "[]()", "{}()",
    "()[]", "[][]", "{}[]",
    "(())[]", "[()][]", "{()}[]"
  ]);
});

typed.ts

/**
 *
 * Constructive demonstration that any (with one or more types)
 * balanced parentheses language can be placed into a 1:1 correspondence
 * with the integers, and then generated in sequence.
 * 
 * We will work along the same lines as the simple balanced parentheses,
 * but introduce a third integer to represent the type of parentheses.
 *
 */

import { NonnegativeTriplet, One, NonnegativePair, Zero } from "./base";

export type Alphabet = string[]; 

/**
 * 
 * The function mapPositiveToNonnegativePair above maps the positive integers (1..∞) to
 * tuples of nonnegative integers (0..∞, 0..∞) by diagonalizing them on
 * a grid like this:
 * 
 *      |  0 |  1 |  2 |  3 |  …
 *      |----|----|----|----|---
 * |  0 |  1 |  4 |  5 | 16 | 17
 * |  1 |  2 |  3 |  6 | 15 | 18
 * |  2 |  9 |  8 |  7 | 14 | 19
 * |  3 | 10 | 11 | 12 | 13 | 20
 * |  … | 25 | 24 | 23 | 22 | 21…
 * 
 * Each cell represents a pair marked by the horizontal and vertical labels. For example,
 * square 11 has a vertical label of 3 and a horizontal label of 1.
 * 
 * This is a 2D grid. Let's add a dimension, so we can support triples. In our case, we do
 * not need the third dimension to handle an infinite number of finite integers, we only
 * need to support a finite set of integers in some range from zero to a maximum number.
 * 
 * We will keep the existing two dimensions for the two numbers that can be any finite
 * number, and use the third for the finite set of finite numbers.
 * 
 * We begin with the upper-left square, the base case. The bottom level will correspond to the
 * third number in the tuple being `0`, the middle level will correspond to `1`, and the top
 * will correspond to `2`:
 * 
 *      |  0 |  …         |  0 |  …         |  0 |  … 
 *      |----|----        |----|----        |----|----
 * |  0 |  1 |       |  0 |  2 |       |  0 |  3 |    
 * |  … |    |       |  … |    |       |  … |    |    
 * 
 * This establishes that `1`, `2`, and `3` correspond to `[0, 0, 0]`, `[0, 0, 1]` and `[0, 0, 2]` respectively.
 * Let's add the next three. We follow the same 2D path as with the simple correspondance:
 * 
 *      |  0 |  1 |  …         |  0 |  1 |  …         |  0 |  1 |  … 
 *      |----|----|----        |----|----|----        |----|----|----
 * |  0 |  1 | 10 |       |  0 |  2 | 11 |       |  0 |  3 | 12 |    
 * |  1 |  4 |  7 |       |  1 |  5 |  8 |       |  1 |  6 |  9 |    
 * |  … |    |    |       |  … |    |    |       |  … |    |    |    
 * 
 * @param positive a positive integer
 * @param numberOfLayers the number of layers
 * @returns a triple of nonnegative integers, two of which are any finite integer,
 *          and the third of which is in a fixed range of 0..numberOfTypes-1
 *          and where numberOfTypes >= 1.
 * 
 */
export function mapPositiveToNonnegativeTriplet(positive: number, numberOfLayers: number): NonnegativeTriplet {

  // erroneous inputs
  if (positive < One) throw new RangeError();
  if (numberOfLayers < One) throw new RangeError();
  if (positive != Math.floor(positive)) throw new RangeError();
  if (numberOfLayers != Math.floor(numberOfLayers)) throw new RangeError();

  const positiveZeroBased = positive - 1;
  const positive2d = Math.floor(positiveZeroBased / numberOfLayers) + 1;
  const z = positiveZeroBased % numberOfLayers;

  if (positive2d === One) return [0, 0, z];
  
  const boundingSquareSideLength = Math.ceil(Math.sqrt(positive2d));

  const innerArea = Math.pow(boundingSquareSideLength - 1, 2);
  const distanceAlongOuterBoxSides = positive2d - innerArea;
  const isInFirstHalfOfTrack = distanceAlongOuterBoxSides <= boundingSquareSideLength;
  const boundingBoxArea = Math.pow(boundingSquareSideLength, 2);
  const boundiingBoxColumnOrRowIndex = boundingSquareSideLength - 1;

  const indices2d: NonnegativePair =
    isInFirstHalfOfTrack
      ? [distanceAlongOuterBoxSides - 1, boundiingBoxColumnOrRowIndex]
      : [boundiingBoxColumnOrRowIndex, boundingBoxArea - positive2d];

  const downAndThenLeft = boundingSquareSideLength % 2 === 1;

  const triplet: NonnegativeTriplet =
    downAndThenLeft
      ? [indices2d[0], indices2d[1], z]
      : [indices2d[1], indices2d[0], z];

  return triplet;
}

/**
 * 
 * Maps a positive number to a typed Dyck word by mapping that integer to a triplet,
 * which in turn maps to a specific pair of symbols and empty or another pair and so
 * on down to one of the base cases.
 *
 * @param X the first symbol of the pair
 * @param Y the second symbol of the pair
 * @param nonnegative a positive or counting number 
 * @returns a string
 */
export function mapNonnegativeToTypedDyckWord(nonnegative: number, ...alphabet: Alphabet): string {

  // See mapPositiveToNonnegativePair for general comments about the agorithm for determening the x and y coördinates

  // erroneous inputs
  if (nonnegative < Zero) throw new RangeError();
  if (nonnegative != Math.floor(nonnegative)) throw new RangeError();

  if (alphabet.length === 0) throw new RangeError();
  if (alphabet.length % 2 === 1) throw new RangeError();
  if (alphabet.length !== (new Set(alphabet)).size) throw new RangeError();

  // degenerate case
  if (nonnegative === 0) return '';

  const numberOfTypes = alphabet.length / 2;

  // recursive case
  const [x, y, z] = mapPositiveToNonnegativeTriplet(nonnegative, numberOfTypes);

  const X = alphabet[z * 2];
  const Y = alphabet[z * 2 + 1];

  if (X == undefined) throw new RangeError();
  if (Y == undefined) throw new RangeError();

  return `${X}${mapNonnegativeToTypedDyckWord(x, ...alphabet)}${Y}${mapNonnegativeToTypedDyckWord(y, ...alphabet)}`;
}

export function * typedDyckWords(...alphabet: Alphabet) {
  let n = 0;

  while (true) {
    yield mapNonnegativeToTypedDyckWord(n++, ...alphabet);
  }
}