1

I've got a two dimensional array of synonyms (or rather, equivalent) words; and a given sentence. I need to return an array of sentences that contain all permutations of words replaced with their synonyms.

Example, given synonyms/equivalences array:

const eqs = [
  ['hi', 'hello', 'hey'],
  ['programmer', 'coder']
]

And 

const sentence = 'hello programmer'

Return (order is not important):

['hello programmer',
 'hi programmer',
 'hey programmer',
 'hello coder',
 'hi coder',
 'hey coder']

I'm not able to find all possible permutations, only some. Here's what I have + Codepen demo

const getAllEquivalentSentences = (sentence, eqs) => {
  const eqSentences = new Set([sentence])
  sentence.split(/\s/).forEach(word => {
    // current is an array of equivalent terms, or array
    // with a single item
    const curr = eqs.find(row => row.includes(word)) || [word]
    curr.forEach(wordEq => {
      if (wordEq !== word) {
        eqSentences.add(sentence.replace(word, wordEq))
      }
    })
  })
  return [...eqSentences]
}

Seems like I'll need a dynamic programming solution, but that's getting too complex for me too fast. Is there a simpler approach that I'm missing?

Namanyay Goel
  • 2,641
  • 3
  • 20
  • 26
  • 1
    Does it has the 2d array or probably have multi-dimension array? – Dipak Feb 07 '18 at 17:18
  • 1
    Interesting challenge. Possible recursive solution: https://codepen.io/thbwd/pen/oEYWBX?editors=0011 – idmean Feb 07 '18 at 17:33
  • Thanks for your comments guys -- @Bergi correctly pointed out that this is a duplicate and I was able to adapt the solution that he linked. It's the cartesian product algorithm and I found an efficient JS solution elsewhere on SO. – Namanyay Goel Feb 08 '18 at 14:40

0 Answers0