javascript - 提高这种组合算法的性能？

Question

我正在研究 this kata来自 Codewars。任务是:

Given a certain number, how many multiples of three could you obtain with its digits?

Supose that you have the number 362. The numbers that can be generated from it are:

362 ----> 3, 6, 2, 36, 63, 62, 26, 32, 23, 236, 263, 326, 362, 623, 632

我编写了以下递归函数来计算所有可能性:

const findMult_3 = (num) => {

  const powerset = (set) => {
    const combinations = []
    const combine = (prefix, chars) => {
      for (let i = 0; i < chars.length; i++) {
        const newPrefix = parseInt(prefix + chars[i])
        if (!combinations.includes(newPrefix)) {
          combinations.push(newPrefix)
        } else {
          console.log('encountered duplicate')
        }
        combine(newPrefix, chars.filter((x, ind) => ind !== i))
      }
    }
    combine('', set)
    return combinations.sort((a, b) => a - b)
  }

  const allCombinations = powerset(num.toString().split(''))
  const factorsOfThree = allCombinations.filter(x => x % 3 === 0).filter(x => x !== 0)

  return [factorsOfThree.length, factorsOfThree.pop()]

}

findMult_3(43522283000229)

我很早就注意到我遇到了 很多 重复案例，因此出现了 console.log('encountered duplicate') 标志。

对于大数，例如 43522283000229，此算法的执行时间非常长。

我怎样才能提高这段代码的性能，还是应该完全废弃它？

Answer 1

对于大多数编码套路，算法的选择远比实现细节重要，但在此之前，让我指出您的实现中最明显的缺陷:

    if (!combinations.includes(newPrefix)) {
      combinations.push(newPrefix)
    } else {
      console.log('encountered duplicate')
    }
    combine(newPrefix, chars.filter((x, ind) => ind !== i))

combinations 是一个数组，includes 通过遍历数组并检查每个元素来工作。也就是说，要检查一个元素是否重复，您要将它与以前遇到的每个组合进行比较。由于其中的数量成倍增加，因此这将非常缓慢。如果您改用字典对象或 Map，您的代码会快得多。

此外，您是否注意到您正在继续生成组合，即使该组合是重复的？这是多余的。

所以廉价的改进是:

const combinations = {};
if (combinations[prefix]) {
  // duplicate, do nothing
} else {
  combinations[prefix] = true;
  combine(...);
}

然而，真正的改进是选择更好的算法。如果您利用问题的数学结构，您可能无需遍历所有解决方案即可找到解决方案的数量。

以下见解可能会有所帮助:

• 一个数能被三整除当且仅当它的数字之和是。
• 一个数字的总和可以被 3 整除当且仅当它们除以 3 的余数之和为 0。
• 输入中数字的顺序无关紧要