如何递归地创建一个包含一组字符的字符串，直到它与所需的字符串匹配？

Question

我想递归地创建每个可能的字符串，直到它匹配另一个。

如果我想创建 "ab"，并具有以下字符集

[
  'a', 'b', 'c',
  'd', 'e', 'f'
]

必须经过：

a
b
c
d
e
f
aa
ab // this

直到停止。

我试过了，但我只能让它与 1 个字符一起工作：

function bruteforceTo(text) {
    const charset = "abdef".split("");
    const bf = bruteforcer(charset);
    let x;

    do {
        x = bf.next().value;
        console.log(x);
    } while (x != text);

    function* bruteforcer(charset) {
        let i = 0;

        while (true) {
            yield charset[i++];
        }
    }
}

console.time();
bruteforceTo("ab");
console.timeEnd();

上面的脚本是我想要构建的东西，而不是完全摆脱它（我喜欢生成器），但如果它不能工作，我很乐意做其他事情。

Answer 1

您要找的是

function* bruteforcer(charset) {
    for (const x of charset)
        yield ""+x;
    for (const x of charset)
        for (const y of charset)
            yield ""+x+y;
    for (const x of charset)
        for (const y of charset)
            for (const z of charset)
                yield ""+x+y+z;
    …
}

要生成这些模式直到任意长度，您需要一个递归函数：

function* bruteforcer(charset) {
    for (let i=1; ; i++)
        yield* bruteforceLength("", i, charset);
}
function* bruteforceLength(prefix, length, charset) {
    … // I'll leave this as an exercise :-)
}

Answer 2

您实际上不需要递归，只需将生成的子字符串放入队列中，然后为每个 'head' 子字符串将 N 个更长的字符串推回。

function *generate(chars) {
    let len = chars.length
    let queue = Array(len).fill(0).map((_, n) => [n])

    while (1) {
        let a = queue.shift()
        yield a.map(n => chars[n]).join('')
        for (let n = a[a.length - 1]; n < len; n++)
            queue.push(a.concat(n))
    }
}

//

let max = 0
for (let p of generate('abcd')) {
    if (max++ > 100)
        break
    document.write(p + ' ')
}

注意这个生成器是无穷无尽的，它不会停止直到你告诉它（或者你内存不足）。

如何递归地创建一个包含一组字符的字符串，直到它与所需的字符串匹配？

How can I recursively create a string with a set of chars until it matches the desired string?

javascript

generator

brute-force