如何在C++中惰性生成多集合的大量组合

你遇到的这个内存溢出问题太典型了——当集合数量K和每个集合的元素数上去之后，总组合数呈指数级增长，一次性生成所有组合必然会把内存撑爆。咱们可以换个思路：不一次性生成所有组合，而是按需逐个生成，让消费者用一个取一个，这样内存占用就只和集合数量K有关，完全不会出现溢出问题。

核心思路：索引进位追踪法 #

这个思路类比数字的进位机制：

• 给每个集合分配一个索引，初始时所有索引都指向对应集合的第一个元素
• 每次根据当前索引生成一个组合
• 然后更新索引：从最后一个集合的索引开始加1，如果索引超过了集合的元素个数，就把它重置为0，同时前一个集合的索引加1（类似十进制加法的进位）
• 重复这个过程，直到第一个集合的索引也无法进位（也就是所有索引都回到初始状态的前一位），就表示所有组合都生成完毕

这种方法的内存开销只有O(K)：只需要保存一个长度为K的索引数组，以及当前生成的单个组合（长度也是K），和总组合数完全无关，哪怕K=20、每个集合5个元素（5^20个组合）也完全没问题。

C++ 实现示例 #

下面是一个简单的生成器类，支持逐个获取组合：

#include <vector>
#include <string>
#include <cassert>

class CombinationGenerator {
private:
    const std::vector<std::vector<std::string>>& sets;
    std::vector<size_t> indices;
    bool has_next;

public:
    // 构造函数，传入要组合的集合列表
    explicit CombinationGenerator(const std::vector<std::vector<std::string>>& input_sets)
        : sets(input_sets), has_next(true) {
        // 初始化所有索引为0，如果有空集合，直接标记为无后续组合
        for (const auto& s : sets) {
            if (s.empty()) {
                has_next = false;
                return;
            }
            indices.push_back(0);
        }
        // 如果没有集合，也标记为无后续
        if (sets.empty()) has_next = false;
    }

    // 判断是否还有下一个组合
    bool hasNext() const {
        return has_next;
    }

    // 获取下一个组合，调用前需要先判断hasNext()
    std::vector<std::string> next() {
        assert(has_next && "No more combinations available");

        // 生成当前索引对应的组合
        std::vector<std::string> combination;
        for (size_t i = 0; i < sets.size(); ++i) {
            combination.push_back(sets[i][indices[i]]);
        }

        // 更新索引，处理进位
        size_t pos = indices.size() - 1;
        while (pos < indices.size()) {
            indices[pos]++;
            if (indices[pos] < sets[pos].size()) {
                // 当前索引没超限，不需要进位，结束更新
                break;
            }
            // 当前索引超限，重置为0，向前进位
            indices[pos] = 0;
            if (pos == 0) {
                // 第一个索引也超限了，说明所有组合都生成完了
                has_next = false;
                break;
            }
            pos--;
        }

        return combination;
    }
};

使用示例 #

#include <iostream>

int main() {
    std::vector<std::vector<std::string>> sets = {
        {"a1", "a2", "a3"},
        {"b1", "b2", "b3", "b4"},
        {"c1", "c2"}
    };

    CombinationGenerator generator(sets);
    while (generator.hasNext()) {
        auto combo = generator.next();
        // 这里可以消费组合，比如打印或者处理
        for (const auto& elem : combo) {
            std::cout << elem << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

为什么这个方法更优？ #

• 内存占用极低：不管总组合数是百万还是万亿，内存只占用O(K)，完全不会触发内存溢出
• 按需生成：消费者可以处理完一个组合再取下一个，不需要等待所有组合生成完毕
• 兼容性好：可以适配任意数量的集合，也支持不同大小的集合，甚至可以处理空集合（直接返回无组合）

如果你需要泛化到其他元素类型（比如int、自定义类），只需要把std::string换成对应的模板类型即可。

内容的提问来源于stack exchange，提问作者Tirtha Pratim Bhattacharjee