Question 50584 in Javascript Question posted in
A very good W3school tutorial can be found here.

How do I generate all variations when only one letter is enclosed in parentheses? – Javascript

The code should generate all variations of a word that have letters in parentheses. Currently, it works when there are multiple letters in the parentheses, but not when there is only one letter inside.

Example:
t(ea)st

test, tast

Here, "test" and "tast" are generated from the word "t(ea)st". That works fine.

But what doesn’t work is when there is only one letter in the parentheses.

Example:
t(e)st

test

Only the word "test" is generated, but it should also generate "tst".
The problem now is that no matter what I try, I can’t get it to generate the word "tst".

If there are multiple parentheses with only one letter inside, as in this example:

t(e)st(s) – then the following words should be generated:

tests, test, tsts, tst

  const generateVariations = (() => {
    const cache = {};

    return (word) => {
      if (cache[word]) {
        return cache[word];
      }

      const variations = [];

      // Find all groups of letters in parentheses
      const groups = word.match(/(([^)]+))/g) || [];

      // Create an array of arrays, where each subarray contains the letters in a group
      const letterArrays = groups.map(group => group.slice(1, -1).split(''));

      // If a group has only one letter, remove the parentheses and add the letter to the list of groups
      const modifiedGroups = groups.reduce((acc, group) => {
        if (group.length === 3) {
          acc.push(group[1]);
        } else {
          acc.push(group);
        }
        return acc;
      }, []);

      // Generate all possible combinations of letters from each group
      const combinations = cartesianProduct(...letterArrays);

      // Generate variations by replacing each group with each combination of letters from that group
      for (const combination of combinations) {
        let newWord = word;
        for (let i = 0; i < modifiedGroups.length; i++) {
          const group = modifiedGroups[i];
          if (group.length === 1) {
            newWord = newWord.replace(`(${group})`, group);
          } else {
            newWord = newWord.replace(groups[i], combination[i]);
          }
        }
        variations.push(newWord);
      }

      cache[word] = variations;
      return variations;
    };
  })();

  function cartesianProduct(...arrays) {
    let result = [[]];
    for (const array of arrays) {
      const newResult = [];
      for (const x of result) {
        for (const y of array) {
          newResult.push([...x, y]);
        }
      }
      result = newResult;
    }
    return result;
  }
Tags:

2

Answers


  1. 0

    You already have a function for cartesian products, all what’s left is to parse your input into an array of arrays, for example:

        input = 't(eo)st(s)'
    arrays = []
    
    input.replace(/((.+?))|([^()]+)/g, (_, br, nobr) => {
        if (nobr)
            arrays.push([nobr])
        else if (br.length === 1)
            arrays.push(['', br])
        else
            arrays.push([...br])
    })
    
    console.log(arrays)

    Then simply apply cartesianProduct(...arrays) and join each result.

    Login or Signup to reply.
  2. 0

    Expand and merge, by splitting each (...) pattern, with a check to see how many letters are in that pattern. If it’s more than one, regular split. If it’s only one, don’t split but just create the array of letters yourself, since you know it needs to be ["", thatOneLetter].

    // Set up a regex that'll match something that's followed
// by a parentheses pair. We'll use this to "cut up" our
// input so we can simply expand one group of letters at
// a time and keep our code nice and simple.
const fractionalRegExp = /([^(]+)(([^)]+))(.*)/;

function expand(word, results=[]) {
  // is there a `(...)` pattern we need to expand?
  const match = word.match(fractionalRegExp);
  // if not, we're done.
  if (match === null) return [word];
  // if there is, branch and expand:
  const [_, prefix, pattern, suffix] = match;
  // (is it one letter, or more than one letter?)
  const letters = (pattern.length === 1) ? [``, pattern] : Array.from(pattern);
  // form new distinct words for each possible letter,
  // expand that, and merge them into the result set.
  letters.forEach(l => results.push(...expand(`${prefix}${l}${suffix}`)));
  return results;
}

console.log(expand(`t(e)st`));
console.log(expand(`t(ea)st`));
console.log(expand(`t(e)st(e)`));
console.log(expand(`t(ea)st(e)`));
console.log(expand(`t(e)st(ea)`));
console.log(expand(`t(ea)st(ea)`));

    And of course, bonus points for rewriting that as a breadth-first expansion so you can use a single function call with a while loop that uses an "strings left to expand" array in addition to results, instead of the much more expensive recursive approach. But that’s an exercise for the reader.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search