获取具有不同部分的整数分区数的有效算法（分区函数 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答案还包括琐碎（单个）分区，但这不会以任何方式影响其质量。

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

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

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

算法

参考

Answer 2

我认为解决这个问题的一个简单而有效的方法是从原始帖子中的Wolfram PartitionsQ 链接显式计算生成函数的系数。

这是一个很好的说明性示例，说明了如何构造生成函数以及如何使用它们来计算解决方案。首先，我们认识到问题可能如下：

Let m_1 + m_2 + ... + m_{n-1} = n where m_j = 0 or m_j = j for all j.

Q(n) is the number of solutions of the equation.

我们可以Q(n)通过构造如下多项式（即生成函数）来求得

(1 + x)(1 + x^2)(1 + x^3)...(1 + x^(n-1))

解的数量是项组合起来得到 的方式的数量，即多项式展开后x^n的系数。x^n因此，我们可以通过简单地执行多项式乘法来解决问题。

def Q(n):
    # Represent polynomial as a list of coefficients from x^0 to x^n.
    # G_0 = 1
    G = [int(g_pow == 0) for g_pow in range(n + 1)]
    for k in range(1, n):
        # G_k = G_{k-1} * (1 + x^k)
        # This is equivalent to adding G shifted to the right by k to G
        # Ignore powers greater than n since we don't need them.
        G = [G[g_pow] if g_pow - k < 0 else G[g_pow] + G[g_pow - k] for g_pow in range(n + 1)]
    return G[n]

计时（1000 次迭代的平均值）

import time
print("n    Time (sec)")
for n in [10, 50, 100, 200, 300, 500, 1000]:
    t0 = time.time()
    for i in range(1000):
        Q(n)
    elapsed = time.time() - t0
    print('%-5d%.08f'%(n, elapsed / 1000))

n    Time (sec)
10   0.00001000
50   0.00017500
100  0.00062900
200  0.00231200
300  0.00561900
500  0.01681900
1000 0.06701700