如何高效获取指定等式的所有可行解？C++算法优化求助

我正在用C++编写算法，用于获取形如x + y * z - c % d / e = 33这类等式的所有有效解。等式中的运算符随机，包含+、-、/、*、%、&、|、^（后三者为位运算符），变量的取值来自固定范围（如1、2、3、4、5）。

当前实现是生成所有可重复排列，再将每个排列代入等式验证是否有效，之后将有效解加入集合中。代码如下：

vector<vector<int>> generate_permutations(int start, int end, int length) {
    vector<vector<int>> result;
    if (length == 0) {
        // Base case: return empty list
        result.push_back({});
        return result;
    }
    // Recursive case: generate permutations of length-1 and add all possible values to the end
    vector<vector<int>> sub_permutations = generate_permutations(start, end, length - 1);
    for (int i = start; i <= end; i++) {
        for (vector<int>& sub_permutation : sub_permutations) {
            sub_permutation.push_back(i);
            result.push_back(sub_permutation);
            sub_permutation.pop_back();
        }
    }
    return result;
}

但即使对于规模适中的取值范围，该实现运行速度也非常慢，想了解是否存在更快的可重复排列生成算法、数学方法来获取所有解，或是更优的实现思路。

一、优化可重复排列的生成方式 #

1. 迭代式生成替代递归 #

递归实现会产生大量临时vector拷贝，内存和时间开销极大。改用迭代方式直接在原数组上修改生成排列，同时避免存储所有排列：

void generate_permutations_iterative(int start, int end, int length, const function<void(const vector<int>&)>& callback) {
    vector<int> current(length, start);
    while (true) {
        callback(current); // 生成一个排列就立即验证，无需全量存储
        // 生成下一个可重复排列
        int pos = length - 1;
        while (pos >= 0 && current[pos] == end) {
            current[pos] = start;
            pos--;
        }
        if (pos < 0) break;
        current[pos]++;
    }
}

这种方式仅保留当前排列的内存空间，避免了递归栈开销和大量数组拷贝。

2. 跳过全量存储环节 #

原代码将所有排列存入vector再遍历验证，内存占用为(end-start+1)^length * length * sizeof(int)，当变量数或取值范围稍大时会直接内存溢出。迭代式生成配合回调逻辑，生成一个就验证一个，用完即丢弃，大幅降低内存压力。

二、数学推导与剪枝优化 #

针对等式结构拆分计算，提前过滤不可能的组合，减少需要验证的排列数量：

• 拆分等式为左右独立部分：比如将x + y*z - c%d/e = 33拆分为(x + y*z) = 33 + (c%d/e)，分别预计算左右两边的所有可能结果，再通过哈希表匹配相等的结果组合。这种拆分可将复杂度从O(N^k)降低为O(N^a) + O(N^b)（a+b=k），比如5个变量拆分为2+3，当N=5时，计算量从3125降至150。
• 基于运算符特性剪枝：
  • 乘法、位运算&/|/^可提前过滤不符合结果奇偶性、位特征的组合；
  • 取模%的结果必然小于除数，若等式某部分要求结果大于除数范围，可直接排除对应除数组合；
  • 整数除法/的结果不大于被除数（除数≥1时），据此可过滤超出范围的组合。

三、表达式计算性能优化 #

1. 硬编码表达式计算逻辑 #

避免每次验证都动态解析表达式，直接将等式的计算逻辑写成硬编码函数，比如针对目标等式：

bool is_valid(int x, int y, int z, int c, int d, int e) {
    // 严格遵循C++运算符优先级
    int val = x + (y * z) - ((c % d) / e);
    return val == 33;
}

这种方式比栈式表达式解析快一个数量级以上。

2. 缓存预计算结果 #

拆分等式后，可将重复计算的子表达式结果缓存。比如预计算所有y*z的可能值存入哈希表，后续验证时直接查表，避免重复计算相同子表达式。

四、并行化处理 #

当变量数和取值范围较大时，可将排列生成任务拆分到多个线程并行处理。例如将取值范围分成若干段，每个线程负责处理一段内的排列生成与验证，最后合并结果。注意用std::mutex保护全局结果集合，或让每个线程先存储局部结果，最后再合并，避免线程安全问题。

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