Python生成非交叉分区求助：算法低效且n=14时内存溢出

n=14时非交叉分区的总数是卡特兰数C₁₄=2674440，原算法慢且内存溢出，核心问题在于重复计算和内存占用过高，以下是针对性优化方案：

核心优化思路 #

1. 利用递归结构+缓存避免重复计算 #

非交叉分区具有天然的递归拆分特性：固定元素1所在的块包含1和k（k∈[1,n]），则区间[2,k-1]和[k+1,n]可独立生成非交叉分区，最终结果由这三部分组合而来。用缓存存储子区间的分区结果，避免重复计算相同区间的分区。

2. 采用紧凑数据结构+懒加载 #

• 用元组块替代多层嵌套列表，减少内存开销：比如用[(1,2), (3,5), (4)]表示分区{{1,2},{3,5},{4}}，元组比列表更节省内存。
• 使用**生成器（yield）**逐个生成分区，而非一次性将所有分区加载到内存。这样处理n=14时，内存仅需保留当前生成的单个分区，不会出现溢出。

3. 减少冗余拷贝 #

递归组合子分区时，复用已有结构而非每次创建新对象，比如用不可变的元组存储块，避免频繁的内存拷贝操作。

示例实现（Python） #

from functools import lru_cache

def non_crossing_partitions(n):
    @lru_cache(maxsize=None)
    def generate(start, end):
        if start > end:
            yield []
            return
        # 遍历元素start所在块的右端点k
        for k in range(start, end + 1):
            # 递归生成左右子区间的分区
            for left in generate(start + 1, k - 1):
                for right in generate(k + 1, end):
                    # 组合当前块与左右分区，用元组存储块减少内存
                    yield [(start, k)] + left + right

    # 若不需要一次性持有所有分区，直接返回生成器即可（内存友好）
    # return generate(1, n)
    # 若需要全部结果，转成列表（n=14时约260万条，需确保内存足够）
    return list(generate(1, n))

额外优化建议 #

• 如果需要处理更大的n（比如n>15），可以考虑用C++实现，利用指针和内存池进一步降低内存占用。
• 若仅需统计数量而非生成所有分区，直接计算卡特兰数即可，无需生成具体分区。

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