How to properly call a recursive function inside a for loop?

Question

I'm trying to implement a method that takes as a parameter: target string and an array with string values in it. The goal is to check if it is possible to construct with array's value, the given target string.The words in array can be used as many times as we want. Example:

console.log(canConstruct("abcdef", ["ab", "abc", "cd", "def", "abcd"])); // suppose to return true

As we can see, by concatenating "abc" and "def" we get the target string of "abcdef" Here is my function implementation:

const canConstruct = function (target, wordBank) {
  if (target === "") return true;
  console.log(target);
  for (let word of wordBank) {
    if (target.startsWith(word)) {
      return canConstruct(target.replace(word, ""), wordBank);
    }
  }

  return false;
};  

Line 2 is a base case for this recursion function, then by iterating through the array check if it starts with the array element, if true then remove that specific subarray and call again the function with the new target string and old array, if false keep iterating through entire function till it hits the base case. So again using the previous example:

console.log(canConstruct("abcdef", ["ab", "abc", "cd", "def", "abcd"]));  // return false

I'm getting false, and by debugging I can see that it didn't iterate the whole array from since first recursive call. I get the following output:

abcdef
cdef
ef
false

Midtown

Answer 1

You are breaking for loop even if you return false and skiping all other combinations that way. So you are founding only one path, in your case

ab
cd

const canConstruct = function (target, wordBank) {
    if (target === "")
        return true;
    for (let word of wordBank) {
        if (target.startsWith(word)) {
            if (canConstruct(target.replace(word, ""), wordBank))//break it only if true
                return true;
        }
    }

    return false;
};
console.log("abcdef", canConstruct("abcdef", ["ab", "abc", "cd", "def", "abcd"]));

console.log("abc1def", canConstruct("abc1def", ["ab", "abc", "cd", "def", "abcd"]));

Sensuous

Answer 2

There's an open question here, to my mind. Can we use the substrings multiple times or only once each? That is, should

canConstruct ("abcabc", ["ab", "abc", "cd", "def", "abcd"])

return true because we can break it down into abc-abc, using the second entry twice?

Or should it return false because we've already used up our abc for the beginning?

These two snippets are variants of your technique with a different style.

The first one assumes that we can use our substrings as often as necessary:

const canConstruct = (word, words) => 
  word.length == 0
    ? true
    : words .some (
        (w) => word .startsWith (w) && canConstruct (word .replace (w, ''), words)
      )

console .log (canConstruct ("abcdef", ["ab", "abc", "cd", "def", "abcd"]))  //=> true
console .log (canConstruct ("abcddc", ["ab", "abc", "cd", "def", "abcd"]))  //=> false
console .log (canConstruct ("abcabc", ["ab", "abc", "cd", "def", "abcd"]))  //=> true

The second one says we can only use each once:

const removeFirst = (x, xs, i = xs.indexOf(x)) =>
  i < 0
    ? [... xs]
    : [... xs .slice (0, i), ... xs .slice (i + 1)]

const canConstruct = (word, words) => 
  word.length == 0
    ? true
    : words .some (
        (w) => word .startsWith (w) && canConstruct (word .replace (w, ''), removeFirst(w, words))
      )

console .log (canConstruct ("abcdef",    ["ab", "abc", "cd", "def", "abcd"]))         //=> true
console .log (canConstruct ("abcddc",    ["ab", "abc", "cd", "def", "abcd"]))         //=> false
console .log (canConstruct ("abcabc",    ["ab", "abc", "cd", "def", "abcd"]))         //=> false
console .log (canConstruct ("abcabc",    ["ab", "abc", "cd", "abc", "def", "abcd"]))  //=> true
console .log (canConstruct ("abcabcabc", ["ab", "abc", "cd", "abc", "def", "abcd"]))  //=> false

Here we use a helper function, removeFirst which returns a copy of an array after removing the first instance of the given value.

Fontainebleau

elegant, ... twice. – Cloud

Beautiful combinatronics. Peter says it all. I hope you don't mind me yanking your test cases for my answer. – Conjoined

@Thankyou: is that a combination of combinatorics and histrionics? :-) And of course you can steal the test cases.. – Fontainebleau

Answer 3

combinatorics

If you have generic functions like combinations and permutations you can solve this problem easily -

function canConstruct (target = "", parts = [])
{ for (c of combinations(parts))
    for (p of permutations(c))
      if (p.join("") == target)
        return true
  return false
}

Where combinations is defined as -

function* combinations (t)
{ if (t.length == 0)
    yield t
  else
    for (const c of combinations(t.slice(1)))
      ( yield c
      , yield [t[0], ...c]
      )
}

And permutations is defined as -

function permutations (t)
{ if (t.length < 2)
    return [t]
  else
    return permutations(t.slice(1))
      .flatMap(p => rotations(p, t[0]))
}

function rotations (t, e)
{ if (t.length == 0)
    return [[e]]
  else
    return [[e,...t], ...rotations(t.slice(1), e).map(r => [t[0], ...r])]
}

Let's test it out -

console.log(canConstruct("abcdef",    ["ab", "abc", "cd", "def", "abcd"]))
console.log(canConstruct("abcddc",    ["ab", "abc", "cd", "def", "abcd"]))
console.log(canConstruct("abcabc",    ["ab", "abc", "cd", "def", "abcd"]))
console.log(canConstruct("abcabc",    ["ab", "abc", "cd", "abc", "def", "abcd"]))
console.log(canConstruct("abcabcabc", ["ab", "abc", "cd", "abc", "def", "abcd"]))

Expand the snippet below to verify the results in your own browser -

function* combinations (t)
{ if (t.length == 0)
    yield t
  else
    for (const c of combinations(t.slice(1)))
      ( yield c
      , yield [t[0], ...c]
      )
}

function permutations (t)
{ if (t.length < 2)
    return [t]
  else
    return permutations(t.slice(1))
      .flatMap(p => rotations(p, t[0]))
}

function rotations (t, e)
{ if (t.length == 0)
    return [[e]]
  else
    return [[e,...t], ...rotations(t.slice(1), e).map(r => [t[0], ...r])]
}

function canConstruct (target = "", parts = [])
{ for (c of combinations(parts))
    for (p of permutations(c))
      if (p.join("") == target)
        return true
  return false
}

console.log(canConstruct("abcdef",    ["ab", "abc", "cd", "def", "abcd"]))
console.log(canConstruct("abcddc",    ["ab", "abc", "cd", "def", "abcd"]))
console.log(canConstruct("abcabc",    ["ab", "abc", "cd", "def", "abcd"]))
console.log(canConstruct("abcabc",    ["ab", "abc", "cd", "abc", "def", "abcd"]))
console.log(canConstruct("abcabcabc", ["ab", "abc", "cd", "abc", "def", "abcd"]))

true
false
false
true
false

Scott's brilliant answer has an adaptation that allows for a given part to be reused multiple times, ie where canConstruct("abab", ["ab"]) is true. I can't see a variant of this answer that easily enables such a behaviour.

---

short-circuit

Above we use a simple implementation of permutations but if we use generators, like we did with combinations, we can achieve a desirable short-circuiting behavior for our program -

function* permutations (t)
{ if (t.length < 2)
    yield t
  else
    for (const p of permutations(t.slice(1))) // <- lazy
      for (const r of rotations(p, t[0]))     // <- lazy
        yield r
}

function* rotations (t, e)
{ if (t.length == 0)
    yield [e]
  else
    yield *chain
      ( [[e, ...t]]
      , map(rotations(t.slice(1), e), r => [t[0], ...r])
      )
}

This depends on two generic functions for working with generators, map and chain -

function* map (t, f)
{ for (const e of t)
    yield f(e)
}

function* chain (...ts)
{ for (const t of ts)
    for (const e of t)
      yield e
}

Implementation of canConstruct does not require any changes. permutations will generate permutations one-by-one and when the return is encountered, no additional permutations will be computed -

function canConstruct (target = "", parts = [])
{ for (c of combinations(parts))
    for (p of permutations(c))
      if (p.join("") == target)
        return true
  return false
}

Expand the snippet below to verify the results in your own browser -

console.log(canConstruct("abcdef",    ["ab", "abc", "cd", "def", "abcd"]))
console.log(canConstruct("abcddc",    ["ab", "abc", "cd", "def", "abcd"]))
console.log(canConstruct("abcabc",    ["ab", "abc", "cd", "def", "abcd"]))
console.log(canConstruct("abcabc",    ["ab", "abc", "cd", "abc", "def", "abcd"]))
console.log(canConstruct("abcabcabc", ["ab", "abc", "cd", "abc", "def", "abcd"]))

function* combinations (t)
{ if (t.length == 0)
    yield t
  else
    for (const c of combinations(t.slice(1)))
      ( yield c
      , yield [t[0], ...c]
      )
}

function* permutations (t)
{ if (t.length < 2)
    yield t
  else
    for (const p of permutations(t.slice(1)))
      for (const r of rotations(p, t[0]))
        yield r
}

function* rotations (t, e)
{ if (t.length == 0)
    yield [e]
  else
    yield *chain
      ( [[e, ...t]]
      , map(rotations(t.slice(1), e), r => [t[0], ...r])
      )
}

function* map (t, f)
{ for (const e of t)
    yield f(e)
}

function* chain (...ts)
{ for (const t of ts)
    for (const e of t)
      yield e
}

function canConstruct (target = "", parts = [])
{ for (c of combinations(parts))
    for (p of permutations(c))
      if (p.join("") == target)
        return true
  return false
}

console.log(canConstruct("abcdef",    ["ab", "abc", "cd", "def", "abcd"]))
console.log(canConstruct("abcddc",    ["ab", "abc", "cd", "def", "abcd"]))
console.log(canConstruct("abcabc",    ["ab", "abc", "cd", "def", "abcd"]))
console.log(canConstruct("abcabc",    ["ab", "abc", "cd", "abc", "def", "abcd"]))
console.log(canConstruct("abcabcabc", ["ab", "abc", "cd", "abc", "def", "abcd"]))

true
false
false
true
false

For additional explanation and other benefits to using generators to solve this problem, see this related Q&A.

Conjoined

Thanks again, I was neither thinking off such a math/theory based approach nor did I consider utilizing a generator function for combinations. Learned and got reminded a lot from your answers. – Cloud

I'm curious about the expected time of this algorithm. The implementation is elegant, but I would worry about needing to calculate all those combinations and then all their permutations if this were ever to be used for large input. I keep wondering if there is some useful approach related to finding De Bruijn sequences. – Fontainebleau

the performance will be significantly lower as this answer does next to nothing to short-circuit like yours does. it's provided more as a proof of connected concepts. – Conjoined

Obviously the latest update fixes the performance concerns I raised. Nicely done! – Fontainebleau

@ScottSauyet thanks for reminding me. Post has been updated :D – Conjoined

Answer 4

The problem solving answer already got provided and was accepted.

Nevertheless anytime before I do work with puzzles of data pattern/structures I try sanitizing/optimizing such data in first place.

Having a look at the OP's term ... "abcdef" ... and the syllables list ... ["ab", "abc", "cd", "def", "abcd"] ... the order of the latter's items could be optimized before feeding it to the OP's recursive approach.

Also if one thinks of syllables within the list which won't be used since none of 'em is a substring of the to be constructed term/word/expression, one might want to discard such items from the syllables list before starting the recursive process.

I would like to provide such an optimizing approach as a pre-stage and in addition to what was already contributed to the OP's problem ...

function orderSubstringsMostMatchingLtrByBoundConfig(a, b) {
  // order most matching from left to right.
  const { term, discard } = this;

  const aIdx = term.indexOf(a); // (>= 0) or (-1)
  const bIdx = term.indexOf(b);

  if (discard) {
    if ((aIdx === -1) && !discard.has(a)) {
      // `a` is not a substring of `term`.
      discard.add(a);
    }
    if ((bIdx === -1) && !discard.has(b)) {
      // `b` is not a substring of `term`.
      discard.add(b);
    }
  }
  return (aIdx - bIdx) || (b.length - a.length);  
}

function sanitizeSyllablesList(list, term) {
  const config = { term, discard: new Set() };

  // do not mutate the `list` argument; create a shallow copy.
  list = [ ...list ].sort(
    orderSubstringsMostMatchingLtrByBoundConfig.bind(config)
  );
  return list.slice(config.discard.size);
}


const syllableList = ['cd', 'foofoo', 'abcd', 'def', 'bar', 'abc', 'bazbizbuz', 'ab'];
const term = "abcdef";

console.log(
  `term: '${ term }', sanitized syllables list:`,
  sanitizeSyllablesList(syllableList, term)
);
console.log('original syllables list:', syllableList);

.as-console-wrapper { min-height: 100%!important; top: 0; }

Or we can make the function a bit more direct by avoiding mutation and variable function contexts ...

const sanitizeSyllables = (list, term) =>
  list
    .map(syllable => ({ syllable, pos: term.indexOf(syllable) }))
    .filter(s => s.pos >= 0)
    .sort((a, b) => a.pos - b.pos)
    .map(s => s.syllable)

const syllables = ['cd', 'foofoo', 'abcd', 'def', 'bar', 'abc', 'bazbizbuz', 'ab'];
const term = "abcdef";

console.log(
  `term: '${ term }', sanitized syllables list:`,
  sanitizeSyllables(syllables, term)
);

console.log('original syllables list:', syllables);

.as-console-wrapper { min-height: 100%!important; top: 0; }

Cloud

Nice optimisation, Peter. This would make a big difference especially if the list of input syllables is significantly large. I hope you don't mind I provided a rewrite of your program with less indirection. Feel free to edit as you see fit. – Conjoined

@Thankyou ... Thank's for all the effort. Since the changes are made in an informative and non offensive way I even enjoy it. And thanks for the undeserved upvote too. – Cloud