在 javascript 中生成所有可能的字母配对且不重复

Question

我正在玩一个使用 Enigma M3 密码的游戏。它本来不应该这样玩，但我发现它很有趣。就目前的线索而言，密码的插板未知。

插头板字符串如下所示：“bq cr di ej kw mt os px uz gh”

以下是此特定插板的规则：

1. 字母只能使用一次：“ab cc de”是无效插件
2. 可以是0-20个字符
3. 必须是偶数个字母：“ab”有效，但“ab c”无效

我正在尝试在 JavaScript 中生成所有可能的组合，但很困难。或者更确切地说，我正在努力以最有效的方式做到这一点。

因为我知道答案插件板很可能是英文的，所以它可能很短；在上述限制下很难想出长短语。所以最好先尝试较短的答案。

在 javascript 中执行此操作最有效的算法是什么？

Answer 1

结果的数量很快就会变成天文数字，但如果目的只是开始生成它们并在时间允许的情况下继续生成，那么生成器在这里似乎是一个有用的工具。

要跟踪哪些字母已被使用，您可以使用位图（26 位），其中 1 位表示该字母仍未使用。

这是一个可能的实现：

// Produce pairings of an exact (even) size
function* generatePairingsOfSize(size, alphabet) {
    if (size == 0) return yield "";
    // Visit each 1-bit (which represents an available letter)
    for (let bits1 = alphabet; bits1; bits1 &= bits1 - 1) {
        const bit1 = bits1 & -bits1; // This is the bit
        for (let bits2 = alphabet ^ bit1; bits2; bits2 &= bits2 - 1) {
            const bit2 = bits2 & -bits2; // ...and a second, distinct bit
            // Get the character pair that is represented by these two bits:
            const s = String.fromCharCode(97 + 31 - Math.clz32(bit1)) + String.fromCharCode(97 + 31 - Math.clz32(bit2));
            // Use recursion to extend smaller strings with the above pair
            for (const result of generatePairingsOfSize(size-2, alphabet ^ bit1 ^ bit2)) {
                yield s + " " + result;                
            }
        } 
    }
}

// Produce pairings of all possible sizes (theoretical maximum is 26)
function* generatePairings() {
    const alphabet = (1 << 26) - 1; // A 1-bit per letter of the alphabet
    for (let size = 0; size <= 26; size += 2) {
        yield* generatePairingsOfSize(size, alphabet);
    }
}

// Get an iterator:
const iter = generatePairings();

// Demo: Using a timer to see the progress:
function loop () {
    const {done, value} = iter.next();
    if (done) return;
    console.log(value);
    setTimeout(loop);
}

loop();