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 , Partition Function Q
编辑:
为避免混淆， DarrylG answer 还包括琐碎的(单个)分区，但这不会以任何方式影响它的质量。
编辑2: jodag (接受的答案)不包括琐碎的分区。

Answer 1

测试了两种算法

简单递推关系

WolframMathword 算法(基于 Georgiadis、Kediaya、Sloane)

Both implemented with Memoization using LRUCache.

Results: WolframeMathword approach orders of magnitude faster.

1. 简单递推关系(带内存)

Reference

代码

@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)

Reference

代码

# 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

Conclusion: This algorithm is orders of magnitude faster than the simple recurrence relationship

算法

Reference