How to generate all possible words from atomic word shapes?

Question

I am working on this code:

const vowels = ['i', 'a', 'u', 'e', 'E', 'U', 'I', 'o', 'A', 'O', 'o#', 'u#', 'e#', 'i#', 'a#']
const consonants = ['m', 'n', 'q', 'g', 'd', 'b', 'p', 't', 'k', 'h', 'l', 'w', 'f', 's', 'C', 'z', 'v', 'y', 'x', 'r', 'c', 'j', 'Q', 'S', 'Z', '\'']
const tones = ['', '+', '-']
const shapes = [
  '{c}{c}{v}{t1}{v}{t2}',
  '{c}{v}{t1}{v}{t2}',
  '{c}{v}{t}',
  '{c}{c}{v}{t}',
  '{c}!{v}{t}',
]

const words = {}

shapes.forEach(shape => {
  words[shape] = generate(shape)
})

function generate(shape) {
  const sets = {
    v: vowels,
    c: consonants,
    t: tones
  }

  const selectors = {}
  const nodes = []
  shape.replace(/{(\w)(\d)?}/g, (_, $1, $2 = '') => {
    selectors[`${$1}${$2}`] = sets[$1]
    nodes.push(`${$1}${$2}`)
    return _
  })

  // getting lost here
  nodes.forEach(node => {
    
  })
}

function randomBetween(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min
}

console.log(words)

The shapes array has stuff like this: {c}{c}{v}{t1}{v}{t2}, where c is for a consonant, v is for a vowel, and t is for a tone (from the 3 sets above). The digits next to the type just makes it so we have unrelated values, whereas the same key like {c}{c} means the same consonant twice, while {c1}{c2} means two different consonants.

The goal is to generate all possible combinations of the shape. How can we do that?

For this shape {c}{v}{t}, we would start to see this result:

mi
me
ma
mo
mu
...
mi+
me+
ma+
...
ni
ne
na
no
nu
...

What I have tried already is this:

function cartesian() {
  var arr = [].slice.call(arguments),
      intLength = arr.length,
      arrHelper = [1],
      arrToReturn = [];

  for (var i = arr.length - 1; i >= 0; i--) {
      arrHelper.unshift(arrHelper[0] * arr[i].length);
  }

  for (var i = 0, l = arrHelper[0]; i < l; i++) {
      arrToReturn.push([]);
      for (var j = 0; j < intLength; j++) {
          arrToReturn[i].push(arr[j][(i / arrHelper[j + 1] | 0) % arr[j].length]);
      }
  }

  return arrToReturn;
}

const vowels = [
  'i',
  'a',
  'u',
  'e',
  'E',
  'U',
  'I',
  'o',
  'A',
  'O',
  'o#',
  'u#',
  'e#',
  'i#',
  'a#',
]

const consonants = [
  'm',
  'n',
  'q',
  'g',
  'd',
  'b',
  'p',
  't',
  'k',
  'h',
  'l',
  'w',
  'f',
  's',
  'C',
  'z',
  'v',
  'y',
  'x',
  'r',
  'c',
  'j',
  'Q',
  'S',
  'Z',
  '\'',
]

const tones = [
  '',
  '+',
  '-',
]

const nasals = [
  '',
  '~',
]

const pharyngeals = [
  '',
  '~',
]

const ejectives = [
  '',
  '!',
]

const implosives = [
  '',
  '?',
]

const shapes = [
  '{c}{c}{v}{t1}{v}{t2}',
  '{c}{v}{t1}{v}{t2}',
  '{c}{v}{t}',
  '{c}{c}{v}{t}',
  '{c}!{v}{t}',
]

const words = {}

shapes.forEach(shape => {
  words[shape] = generate(shape)
})

function generate(shape) {
  const sets = {
    v: vowels,
    c: consonants,
    t: tones,
    n: nasals,
    p: pharyngeals
  }

  const selectors = {}
  const string = []
  shape.replace(/{(\w)(\d)?}/g, (_, $1, $2 = '') => {
    selectors[`${$1}${$2}`] = sets[$1]
    string.push(`${$1}${$2}`)
    return _
  })

  const keys = Object.keys(selectors)
  const values = keys.map(selector => selectors[selector])
  const combinations = cartesian(...values)
    .map(nodes => {
      const map = {}
      nodes.forEach((node, i) => map[keys[i]] = node)
      return map
    })

  const result = []
  combinations.forEach(combination => {
    const out = shape.replace(/{(\w+)}/g, (_, $1) => {
      return combination[$1]
    })
    result.push(out)
  })

  return result
}

function randomBetween(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min
}

Here is a version that generates a random value, there are too many values to store in memory.

const vowels = [
  'i',
  'a',
  'u',
  'e',
  'E',
  'U',
  'I',
  'o',
  'A',
  'O',
  'o#',
  'u#',
  'e#',
  'i#',
  'a#',
]

const consonants = [
  'm',
  'n',
  'q',
  'g',
  'd',
  'b',
  'p',
  't',
  'k',
  'h',
  'l',
  'w',
  'f',
  's',
  'C',
  'z',
  'v',
  'y',
  'x',
  'r',
  'c',
  'j',
  'Q',
  'S',
  'Z',
  '\'',
]

const tones = [
  '',
  '+',
  '-',
]

const nasals = [
  '',
  '~',
]

const focusings = [
  '',
  '~',
  '=',
  'Y',
  'w',
  'h',
]

const explosivities = [
  '',
  '!',
  '?',
]

const shapes = [
  '{c}{f}{e}{v}{t}{n}',
  '{c}{f}{e}{v}{t1}{n}{v}{t2}{n}',
  '{c}{f}{e}{c}{f}{e}{v}{t}{n}',
  '{c}{f}{e}{c}{f}{e}{v}{t1}{n}{v}{t2}{n}',
  '{c1}{f1}{e1}{c2}{f2}{e2}{v}{t}{n}',
  '{c}{f}{e}{v1}{t}{n}{v2}{t}{n}',
  '{c}{f}{e}{c}{f}{e}{v1}{t}{n}{v2}{t}{n}',
]

function generate() {
  const sets = {
    v: vowels,
    c: consonants,
    t: tones,
    n: nasals,
    f: focusings,
    e: explosivities
  }

  const shape = shapes[randomBetween(0, shapes.length - 1)]

  const selectors = {}
  const string = []
  shape.replace(/{(\w)(\d)?}/g, (_, $1, $2 = '') => {
    selectors[`${$1}${$2}`] = sets[$1]
    string.push(`${$1}${$2}`)
    return _
  })

  const values = {}
  Object.keys(selectors).forEach(selector => {
    const set = selectors[selector]
    const idx = randomBetween(0, set.length - 1)
    values[selector] = set[idx]
  })

  const result = string.map(selector => values[selector]).join('')

  return result
}

function randomBetween(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min
}

console.log(generate())
console.log(generate())
console.log(generate())
console.log(generate())

user_3186088 · Answer

This is not an exact answer to your question -- so I apologize to the Stack Overflow purists -- but it might nonetheless be helpful to you, depending on your goals. So thought I'd share anyway. :)

Typescript's template literal types can get us part of the way. We start by defining some string union types:

type Vowel = 'i' | 'a' | 'u' | 'e' | 'E' | 'U' | 'I' | 'o' | 'A' | 'O' | 'o#' | 'u#' | 'e#' | 'i#' | 'a#'
type Consonant = 'm' | 'n' | 'q' | 'g' | 'd' | 'b' | 'p' | 't' | 'k' | 'h' | 'l' | 'w' | 'f' | 's' | 'C' | 'z' | 'v' | 'y' | 'x' | 'r' | 'c' | 'j' | 'Q' | 'S' | 'Z' | '\''
type Tone = '' | '+' | '-'

This lets us use a template literal type to create every enumeration for a given shape/pattern; eg, for '{c}{v}{t}':

type ShapeString = `${Consonant}${Vowel}${Tone}`

This, in turn, allows us to define a mapped type that represents a dictionary for our ShapeString:

type EveryCombinationOfShapeString = { [K in ShapeString]: K}

Now your IDE should be able to help enumerate an object of that type:

const Dictionary: EveryCombinationOfShapeString = {
  // ...
  "Ce-": 'Ce-',
  "Ci#": 'Ci#',
  "Ci#+": 'Ci#+',
  "Ci#-": 'Ci#-',
  // ...
}

^ I won't post the whole thing here, because it's already 1000+ lines at just 3 characters, but I can confirm that WebStorm was able to implement all members of this object for me in ~30s or so.

I know this ignores the {c1}{c1} aspect of your question, and also pulls in a new language, but I hope it's helpful nonetheless. Maybe you could use Object.values over that object and do some additional filtering/mapping.

(edits for clarity, renaming, documentation links, etc.)

How to generate all possible words from atomic word shapes?

1 Answers