How can I generate all possible combinations of a character substitution in a word in JavaScript?

Question

Consider the following made up word: "zazaza".

I'm trying to come up with a function, that given a letter to replace and a word to match that letter against, generates all combinations of that letter substitution.

I have a JSON that contains the letter to match and the letter to replace, like this:

var replacement = {original: 'Z', replace: 'S'};

The full example would be something like this:

var generatedCombinations = generateAllCombinations(replacement, "zazaza");

And the array would contain:

zazaza
sazaza
sasaza
sasasa
zasasa
zazasa
...

This sounds like it would be easier to implement with recursion, but as I understand it, function calls in JavaScript can be expensive so I am not sure about taking that approach. I think my main problem is how to ensure that I am generating all the combinations.

The purpose of creating this array is so I can match all these words against another, so I'm not sure if there's a regex expression that can do this and that would be more practical to implement.

Answer 1

There are N possible positions to insert the replacement letter and your task boils down to generating all possible subsets of a set of positions. This can be done by iterating from 0 to 2^N, where each iteration emits a subset containing elements corresponding to the set bits of the loop counter.

This is very efficient, but only works for max 32 elements due to javascript limitations.

In the general case, recursion is the way to go, for example:

let powerset = a => _powerset([[]], a);

let _powerset = (out, rest) =>
    rest.length ?
        _powerset(
            out.concat(out.map(x => x.concat(rest[0]))),
            rest.slice(1))
        : out;

Note that this function is tail-recursive, so modern JS engines will be able to optimize function calls away.

(bored waiting for V8 to compile, so here's the full code) ;)

let powerset = a => _powerset([[]], a);

let _powerset = (out, rest) =>
    rest.length ?
        _powerset(
            out.concat(out.map(x => x.concat(rest[0]))),
            rest.slice(1))
        : out;

let enumerate = (str, char) => [...str]
    .map((c, i) => [c, i])
    .filter(p => p[0] === char)
    .map(p => p[1]);

let translate = (str, pos, replace) => [...str]
    .map((c, i) => pos.includes(i) ? replace : c) // @todo: optimize me
    .join('');


let allReplacements = (str, char, replace) =>
    powerset(enumerate(str, char)).map(pos => translate(str, pos, replace));


console.log(allReplacements('_abc_def_x', '_', '@'));