代码之家  ›  专栏  ›  技术社区  ›  valerii15298

所有可能的不同的不递减的数字序列(组合),以快速达到给定的总和

  •  0
  • valerii15298  · 技术社区  · 2 年前

    我需要数出所有可能的数字组合才能达到给定的总和。 它们应该是非递减的(下一个数字应该大于或等于前一个)。 以下是JavaScript代码和解决问题的示例,但它对以下数字有效期很长 200 :

    function spreadInteger(N) {
      function generateCombinations(current, remaining, start) {
        if (remaining === 0) {
          console.log(current.join(" ")); // here I can just put counter and remove `current` variable from arguments to make it faster but it is will be still not enough
          return;
        }
        for (let i = start; i <= remaining; i++) {
          generateCombinations([...current, i], remaining - i, i);
        }
      }
      generateCombinations([], N, 1);
    }
    
    // spreadInteger(1); // 1 combination
    // 1
    
    // spreadInteger(2); // 2 combinations
    // 1 1
    // 2
    
    // spreadInteger(3); // 3 combinations
    // 1 1 1
    // 1 2
    // 3
    
    // spreadInteger(4); // 5 combinations
    // 1 1 1 1
    // 1 1 2
    // 1 3
    // 2 2
    // 4
    
    // spreadInteger(5); // 7 combinations
    // 1 1 1 1 1
    // 1 1 1 2
    // 1 1 3
    // 1 2 2
    // 1 4
    // 2 3
    // 5
    

    我怎样才能数得更快? 我不需要记录所有的组合,我只需要计算给定数字N有多少这样的组合。 我不关心用编程语言来解决它。我只关心解决方案,所以即使是伪代码的答案也会被接受。 如果可以加快计算速度,也可以假设没有内存限制。

    1 回复  |  直到 2 年前
        1
  •  2
  •   Dillon Davis    2 年前

    你想数一下 分区 n 。这样做的数学函数是 partition function 它在wiki页面上列出了一个很好的递归关系:

    p(n) = sum((-1^k) * p(n - k*(3*k-1)/2))
    

    减去的值 n 在每个学期中 pentagonal numbers 它们本身具有很好的闭式表达式:

    P_n = (3*n^2 - n) / 2
    

    这意味着您可以计算一个整数的分区数 n 在里面 O(n^1.5) 时间通过建立一个表 p(x) 值来自 1..n 递增。