javascript - 如何在 JavaScript 中获取带有给定替换的字符串的所有组合？

Question

我想返回字符串的所有可能组合，同时保持所有内容的正确顺序并避免重复。这是什么原因？我想通过允许混合使用假名和汉字来使一些日语测验的答案更加灵活。因此，我需要所有可能的组合来与用户的答案进行比较。

这是函数的当前语法:( located here )

Genki.getAlts('{月曜日}と{水曜日}と{金曜日}に{日本語}のクラスがあります', 'げつようび|すいようび|きんようび|にほんご');

花括号内的文本是将被第二个参数中的替代文本替换的文本，我将它们简称为 替换 .但是，替代文本应该只替换相同的索引。那是:

月曜日只能换成げつようび

水曜日只能换成すいようび

等等...

举一个简单的例子来说明我想要实现的目标。说我有以下几点:

Genki.getAlts('...{A}...{B}...', '1|2', true);

我希望它返回所有组合，如下所示。

'...1...{B}...'
'...1...2...'
'...{A}...2...'
'...{A}...{B}...'

当前的实现适用于 2-7 个给定的替换，但是当给定超过 8 个时，总组合覆盖率开始下降。可以使用以下公式计算组合总数: Math.pow(2, 8) ，这将返回 8 个替换的“256”个组合，但目前 getAlts() 只返回 234 个组合，这意味着我们缺少 22 个，只给了我们 91% 的组合覆盖率。

所以这就是我目前陷入困境的地方。您可以通过以下链接查看当前代码。 (是的，这有点骇人听闻)通过自学，我尽我所能获得尽可能多的组合，但我担心我的数学技能不是那么好。我确信有一个更简单的方法来解决这个问题，我只是想多了。

代码: Genki.getAlts()

测试页: lesson-4/workbook-6 || page source (控制台将显示所有当前组合)

作为当前算法失败的一个例子，打开你的控制台，你应该看到最后一个问题的警告，说的是:

234/256 (91.40625% combo coverage for 8 replacements; 22 missing combos

此问题的代码:

Genki.getAlts('{1:私}はきのう{学校}で{1:写真}を{1:撮}りました。{2:私}は{家}でも{2:写真}を{2:撮}りました。', 'わたし|がっこう|しゃしん|と|わたし|いえ|しゃしん|と', true);

还有一个更简单的，有 10 个替换项，用于在控制台中执行测试用例:

Genki.getAlts('{A}{B}{C}{D}{E}{F}{G}{H}{I}{J}', '1|2|3|4|5|6|7|8|9|10', true)

无论指定了多少替换，是否有任何可能且简单的方法来返回字符串的所有组合？虽然我知道有多少组合，但使用 Math.pow(2, n) ，我不确定如何正确获取它们。

我很乐意听到有关实现这一目标的现有算法或框架。

PS:事实上，该算法对于 2-7 次替换工作正常，很少有问题达到或超过此阈值。但是，当他们这样做时，用户的答案可能会被错误地标记为错误，我想避免这种情况。最简单的解决方案显然是避免打破 7，但这并不总是可能的，而且，我目前实现这一目标的方式并不是最佳的，所以我也想对其进行优化。

Answer 1

您可以使用二进制数学来解决这个问题。这是一种生成字符串数组的方法:

function getAlts(str, alt) {
  var subs = alt.split('|');
  var length = subs.length;
  var permutations = Math.pow(2, length);
  var results = [];

  for (var i = 0; i < permutations; ++i) {
    var bitIndex = 0;
    var result = str.replace(/\{(.*?)\}/g, function (match, p1) {
      var subIndex = bitIndex++;
      var bit = length - 1 - subIndex;
      return ((1 << bit) & i) ? subs[subIndex] : p1;
    });

    results.push(result);
  }

  return results;
}

console.log(getAlts('...{A}...{B}...', '1|2'));

或者如果你能够使用 ES6 (ECMAScript 2015)，你可以写一个 generator function使用更少的内存:

function* getAlts(str, alt) {
  var subs = alt.split('|');
  var length = subs.length;
  var permutations = Math.pow(2, length);

  for (var i = 0; i < permutations; ++i) {
    var bitIndex = 0;
    var result = str.replace(/\{(.*?)\}/g, function (match, p1) {
      var subIndex = bitIndex++;
      var bit = length - 1 - subIndex;
      return ((1 << bit) & i) ? subs[subIndex] : p1;
    });

    yield result;
  }
}

var results = getAlts('{A}{B}{C}{D}{E}{F}{G}{H}{I}', '1|2|3|4|5|6|7|8|9');
var total = 0;

for (var result of results) {
  console.log(result);
  total++;
}

console.log('total:', total);