如何用OpenMP并行化无放回组合的双层循环结构？

核心并行思路：按组合规模（nCi）拆分任务 #

不同规模的组合（如nC1、nC15、nC29）完全相互独立，直接给每个i（从1到n-1）分配单独线程即可，线程间无依赖也无需竞争。用OpenMP的parallel for就能实现，重点只并行外层遍历i的循环——单个nCi组合的生成逻辑保持串行即可，因为单组生成的计算量远不如跨规模任务拆分的收益高。

改造后的核心代码示例：

// 外层遍历组合规模i的循环，开启并行
#pragma omp parallel for schedule(dynamic)
for (int i = 1; i < n; ++i) {
    std::vector<int> combo(i);
    std::iota(combo.begin(), combo.end(), 0); // 初始化有序组合
    do {
        // 存储当前组合
        thread_local std::vector<std::vector<int>> local_storage;
        local_storage.push_back(combo);
        
        // 生成补集并存储（用双指针法替代二分查找，更快）
        std::vector<int> complement;
        complement.reserve(n - i);
        int combo_idx = 0;
        for (int j = 0; j < n; ++j) {
            if (combo_idx < i && combo[combo_idx] == j) {
                combo_idx++;
            } else {
                complement.push_back(j);
            }
        }
        local_storage.push_back(complement);
        
        // 此处可改为直接写入文件，避免内存溢出
        // write_to_file(combo);
        // write_to_file(complement);
    } while (std::next_permutation(combo.begin(), combo.end()));
    
    // 最后合并线程局部容器到全局（需加临界区）
    #pragma omp critical
    global_storage.insert(global_storage.end(), local_storage.begin(), local_storage.end());
}

用schedule(dynamic)是因为不同i对应的组合数量差异极大（比如n=30时，30C15有1.5亿个，而30C1仅30个），动态调度能让线程负载更均衡，避免部分线程闲置。

关于std::sort的并行化建议 #

分两种场景判断：

• 单个组合内部排序：单个组合最多30个元素，排序耗时可以忽略，完全没必要并行——并行的线程开销反而会拖慢速度。
• 全局容器整体排序：n=30时总组合数超10亿，整体排序确实耗时。如果用C++17及以上，可以直接用并行排序：

#include <execution>
std::sort(std::execution::par, global_storage.begin(), global_storage.end());

或者用OpenMP包裹串行sort（需编译器支持OpenMP 4.5+）：

#pragma omp parallel
{
    std::sort(global_storage.begin(), global_storage.end());
}

注意：并行生成组合时，绝对不能直接往全局std::vector插元素，必须用线程局部容器暂存，最后再合并，否则会有数据竞争导致结果错误。

额外优化点 #

1. 内存优化：n=30时总组合数超10亿，全存内存会占100GB以上，建议边生成边写入文件，避免swap拖慢速度。
2. 编译优化：编译时加-O3 -fopenmp，最大化串行代码的执行效率。
3. 避免重复计算：nCi和nC(n-i)的补集是互相对应的，可以只计算i从1到n/2，直接生成组合和补集，减少一半循环量。

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