代码之家 › 专栏 › 技术社区 › João Paiva

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

array-algorithms algorithm regex javascript

João Paiva · 技术社区 · 7 年前

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

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

完整示例如下:

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

数组将包含:

zazaza
sazaza
sasaza
sasasa
zasasa
zazasa
...

创建这个数组的目的是让我可以将所有这些单词与另一个单词进行匹配,所以我不确定是否有正则表达式可以做到这一点,并且更易于实现。

1 回复 | 直到 7 年前

georg 7 年前

有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引擎将能够优化函数调用。

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

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前