用于获得具有不同部分的整数的分区数的有效算法（分区函数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左右才相当有效。而且由于我只需要组合的[[number

，而不是组合本身Partition Function Q应该可以解决问题。有人知道如何有效地实施吗？ 有关此问题的更多信息：OEIS，Partition Function Q

编辑：

[为了避免造成混乱，可接受的答案还包括琐碎的（单个）分区，但这不会以任何方式影响其质量。

我需要创建一个将接受一个参数int并输出int的函数，该int表示输入整数分区的不同部分的数量。即，输入：3->输出：1-> {1，2} ...

Answer 1

经过测试的两种算法

Answer 2

您可以将您链接的Mathematica文章中的方程式8、9和10的递归记为N，用于在N运行时中进行二次运算。

Answer 3

def partQ(n):

    result = []

    def rec(part, tgt, allowed):
        if tgt == 0:
            result.append(sorted(part))
        elif tgt > 0:
            for i in allowed:
                rec(part + [i], tgt - i, allowed - set(range(1, i + 1)))

    rec([], n, set(range(1, n)))

    return result