如何更快实现整数有序分拆？有无itertools内置方案？

关于内置解决方案 #

Python的itertools模块里没有直接生成整数有序分拆的内置函数，你需要自己实现或采用更高效的思路替代“生成无序分拆+全排列”的方法——后者会产生大量重复计算（比如分拆含重复元素时，permutations会生成重复结果，还需用set去重，严重影响效率）。

更高效的直接生成有序分拆的方法 #

有序分拆的本质等价于在n-1个“空隙”中选择若干位置插入分隔符。例如n=4，可看作数字序列1 1 1 1，存在3个空隙：1|1|1|1，每个空隙可选插入或不插入分隔符，对应不同的有序分拆：

• 不插任何分隔符：[4]
• 插第一个空隙：[1,3]
• 插第二个空隙：[2,2]
• 插第三个空隙：[3,1]
• 插第一和第二个：[1,1,2]
• 插第一和第三个：[1,2,1]
• 插第二和第三个：[2,1,1]
• 插所有三个：[1,1,1,1]

基于这个逻辑，可直接生成所有有序分拆，效率远高于先无序再排列的方式，因为完全避免了重复计算。以下是两种高效实现：

方法1：基于二进制位的生成 #

利用n-1位二进制数表示分隔符的选择，每一位对应一个空隙是否插入分隔符：

def ordered_partitions(n):
    if n == 0:
        yield []
        return
    # 遍历n-1位的所有二进制数，共2^(n-1)种可能
    for mask in range(1 << (n-1)):
        partition = []
        current = 1
        for i in range(n-1):
            if mask & (1 << i):
                partition.append(current)
                current = 1
            else:
                current += 1
        partition.append(current)
        yield partition

方法2：迭代式构建分拆 #

如果n较大，二进制位方法可能存在内存限制（但n不大时足够高效），可以用栈实现迭代式的分拆构建：

def ordered_partitions_iter(n):
    stack = [(n, [])]
    while stack:
        remaining, path = stack.pop()
        if remaining == 0:
            yield path
            continue
        # 每次取1到remaining的数作为下一个分拆项
        for i in range(1, remaining + 1):
            stack.append((remaining - i, path + [i]))

性能对比 #

和你原有的“accel_asc + permutations + set”方案相比，上述直接生成的方法：

• 不会生成重复结果，无需额外去重操作
• 时间复杂度更低，n越大优势越明显（例如n=10时，有序分拆共512种，而无序分拆仅42种，原方案会对每个无序分拆生成大量重复排列再去重，浪费大量计算资源）

内容的提问来源于stack exchange，提问作者user3310334