如何高效计算非负整数n元组的promote操作闭包？

问题明确 #

• 设n为正整数，S为一组非负整数n元组（例如n=3时，S可以是{(1,2,0), (1,0,1)}）
• promote操作：输入非负整数n元组(t₁,t₂,…,tₙ)、满足tᵢ>0的索引i，以及小于i的索引j，返回新元组——仅将j位置的值加1，i位置的值减1。例：对(1,2,3,4,5)执行i=5、j=2的promote操作，得到(1,3,3,4,4)
• 闭包：从S中元素出发，通过0次或多次promote操作能得到的所有元组集合。例：S={(1,2,0), (1,0,1)}的闭包为{(2,0,0), (1,1,0), (1,0,1), (3,0,0), (2,1,0), (1,2,0)}

现有思路分析 #

• 思路1（BFS遍历）：初始化结果集为S，对结果集中所有元组执行所有可能的promote操作，将新元组加入结果集并重复过程。本质是问题建模为有向图后的BFS，但存在大量重复计算——同一元组会被多次生成和处理。
• 思路2（极小元组优化）：仅针对某排序下的极小元组执行操作，但不确定如何并行化。这里的“极小元组”指无法被其他元组通过promote操作生成的元素，处理这类元组可避免重复处理已能被生成的元素。
• 思路3（函数式实现）：希望用简洁的函数式风格编写代码，但核心需求仍是保证时间效率。

高效实现方案 #

1. 带去重的BFS优化 #

针对思路1的重复问题，用哈希集合存储已生成的元组（比如Python中将元组转为tuple类型，天然可哈希），每次生成新元组时先检查是否已在集合中，仅将未出现的元组加入队列和结果集，彻底避免重复计算。
示例代码：

def compute_closure(S, n):
    from collections import deque
    visited = set(S)
    queue = deque(S)
    while queue:
        current = queue.popleft()
        # 遍历所有合法的i和j（注意索引从0开始）
        for i in range(n):
            if current[i] == 0:
                continue
            for j in range(i):
                new_tuple = list(current)
                new_tuple[j] += 1
                new_tuple[i] -= 1
                new_tuple = tuple(new_tuple)
                if new_tuple not in visited:
                    visited.add(new_tuple)
                    queue.append(new_tuple)
    return visited

2. 极小元组的并行化处理 #

首先定义偏序关系：若元组a可通过若干次promote操作得到元组b，则称a ≥ b（b是a的后代）。闭包中的元组可被划分为若干由极小元（无法被其他元组生成的元素）主导的链。
并行化步骤：

1. 筛选S中的极小元：遍历S中的每个元组，检查是否存在其他元组能通过promote操作生成它，保留无法被生成的元组作为极小元。
2. 为每个极小元分配独立的计算线程/进程，单独计算该极小元生成的闭包子集。
3. 合并所有子集，通过哈希集合去重得到完整闭包。
   这种方式避免了线程间的重复计算，因为不同极小元生成的子集交集仅可能是极小元本身，合并成本极低。

3. 函数式风格实现 #

利用递归、生成器等函数式特性，实现简洁且高效的版本：

def generate_promotes(tuple_, n):
    """生成一个元组所有可能的promote结果"""
    for i in range(n):
        if tuple_[i] == 0:
            continue
        for j in range(i):
            lst = list(tuple_)
            lst[j] += 1
            lst[i] -= 1
            yield tuple(lst)

def compute_closure_func(S, n):
    visited = set(S)
    def helper(current_batch):
        """递归处理当前批次的元组，生成新元素"""
        new_elements = set()
        for t in current_batch:
            for p in generate_promotes(t, n):
                if p not in visited:
                    visited.add(p)
                    new_elements.add(p)
        return visited if not new_elements else helper(new_elements)
    return helper(S)

该版本用生成器懒加载promote结果，递归处理新生成的元组，符合函数式编程的简洁性，同时通过visited集合保证效率。

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