python - 获取具有不同部分的整数分区数的有效算法（分区函数 Q）

Question

我需要创建一个函数，该函数将采用一个参数int和输出int，它表示输入整数分区的不同部分的数量。即，

input:3 -> output: 1 -> {1, 2}
input:6 -> output: 3 -> {1, 2, 3}, {2, 4}, {1, 5}
...

因为我只寻找不同的部分，所以不允许这样的事情：

4 -> {1, 1, 1, 1} or {1, 1, 2}

到目前为止，我已经设法提出了一些算法，这些算法可以找到所有可能的组合，但它们非常缓慢且仅在大约之前有效n=100。而且由于我只需要组合数量而不是组合本身，因此分区函数 Q应该可以解决问题。有人知道如何有效地实现这一点吗？

有关该问题的更多信息：OEIS，分区函数 Q

编辑：

为避免任何混淆，DarrylG答案还包括琐碎（单个）分区，但这不会以任何方式影响它的质量。

编辑2：（jodag接受的答案）不包括琐碎的分区。

标签： pythonalgorithmpartitioning

Answer 1

测试了两种算法

1. 简单的递归关系

2. WolframMathword 算法（基于 Georgiadis、Kediaya、Sloane）

两者都通过使用 LRUCache 的 Memoization 实现。

结果：WolframeMathword 接近数量级的速度更快。

1.简单的递归关系（带记忆）

参考

代码

@lru_cache(maxsize=None)
def p(n, d=0):
  if n:
    return sum(p(n-k, n-2*k+1) for k in range(1, n-d+1))
  else:
    return 1

表现

n    Time (sec)
10   time elapsed: 0.0020
50   time elapsed: 0.5530
100  time elapsed: 8.7430
200  time elapsed: 168.5830

2. WolframMathword 算法

（基于 Georgiadis、Kediaya、Sloane）

参考

代码

# Implementation of q recurrence
# https://mathworld.wolfram.com/PartitionFunctionQ.html
class PartitionQ():
  def __init__(self, MAXN):
    self.MAXN = MAXN
    self.j_seq = self.calc_j_seq(MAXN)

  @lru_cache
  def q(self, n):
    " Q strict partition function "
    assert n < self.MAXN
    if n == 0:
      return 1

    sqrt_n = int(sqrt(n)) + 1
    temp = sum(((-1)**(k+1))*self.q(n-k*k) for k in range(1, sqrt_n))

    return 2*temp + self.s(n)

  def s(self, n):
    if n in self.j_seq:
      return (-1)**self.j_seq[n]
    else:
      return 0

  def calc_j_seq(self, MAX_N):
    """ Used to determine if n of form j*(3*j (+/-) 1) / 2 
        by creating a dictionary of n, j value pairs "
    result = {}
    j = 0
    valn = -1
    while valn <= MAX_N:
      jj = 3*j*j
      valp, valn = (jj - j)//2, (jj+j)//2
      result[valp] = j
      result[valn] = j
      j += 1

    return result

表现

n    Time (sec)
10   time elapsed: 0.00087
50   time elapsed: 0.00059
100  time elapsed: 0.00125
200  time elapsed: 0.10933

结论：该算法比简单的递归关系快几个数量级

算法

参考