javascript - 如何在 JavaScript 中生成单词中字符替换的所有可能组合？

Question

考虑以下组成的单词:“zazaza”。

我试图想出一个函数，给定一个要替换的字母和一个匹配该字母的单词，生成该字母替换的所有组合。

我有一个 JSON，其中包含要匹配的字母和要替换的字母，如下所示:

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

完整的例子是这样的:

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

数组将包含:

zazaza
sazaza
sasaza
sasasa
zasasa
zazasa
...

这听起来好像用递归更容易实现，但据我所知，JavaScript 中的函数调用可能很昂贵，所以我不确定是否采用这种方法。我认为我的主要问题是如何确保生成所有组合。

创建这个数组的目的是让我可以将所有这些词与另一个词进行匹配，所以我不确定是否有一个正则表达式可以做到这一点，而且实现起来会更实用。

Answer 1

有 N 个可能的位置可以插入替换字母，您的任务归结为生成一组位置的所有可能子集。这可以通过从 0 迭代到 2^N 来完成，其中每次迭代都会发出一个子集，其中包含与循环计数器的设置位相对应的元素。

这是非常有效的，但由于 javascript 的限制，最多只适用于 32 个元素。

在一般情况下，递归是可行的方法，例如:

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;

请注意，此函数是尾递归的，因此现代 JS 引擎将能够优化函数调用。

(无聊等待 V8 编译，所以这是完整的代码)；)

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', '_', '@'));