backtracking combinator

bt-search.coffee

# searches a combination of the given elements that matches toMatch
#  @param c array - initially empty, carries the current combination throught
#                   the recursion
#  @param els array - the predefined set of elements
#  @param toMatch string - the rest-string to be matched with the elements
#
#  @return an array of combinations that recursively match
searchCombination = (c, els, rest) ->
  return c if rest.length==0

  searchCombination(c.concat([el]), els, rest.slice(el.length)) \
      for el in els when rest.indexOf(el) == 0

# test
console.log(JSON.stringify(
  searchCombination(
    c=[],
    els=['F', 'FN', 'O', 'R', 'RD', 'D'],
    rest='FNORD'
  )
))

bt-search.js

(function() {
  var c, els, rest, searchCombination;

  searchCombination = function(c, els, rest) {
    var el, _i, _len, _results;
    if (rest.length === 0) return c;
    _results = [];
    for (_i = 0, _len = els.length; _i < _len; _i++) {
      el = els[_i];
      if (rest.indexOf(el) === 0) {
        _results.push(searchCombination(c.concat([el]), els, rest.slice(el.length)));
      }
    }
    return _results;
  };

  console.log(JSON.stringify(searchCombination(c = [], els = ['F', 'FN', 'O', 'R', 'RD', 'D'], rest = 'FNORD')));

}).call(this);