假设有一个大小为 N 的向量 VA,每个元素都是另一个类型为 T 的向量。对类型 T 进行一个操作并返回一个类型为 T 的新值,即bool merge(T a, T b, T &ret);
。如果a和c可以合并,则将结果存入ret
并返回true;否则,返回假。合并操作是反射和传递的。
如果出现以下任一情况,则可以找到解决方案:
- ∃ x 0 , x 1 , ..., x N-1。合并(VA[0][x 0 ],VA[1][x 1 ],合并(VA[2][x 2 ],...,合并(VA[N-2][x N-2 ], VA[N-1][x N-1 ], ret)...));
- 可以合并来自 N-1 (不是 N )子向量的任何元素(选择任何 N-1 ,只有一个例外)。
例如:VA 的大小为 3。元素 a 可以与元素 b 合并,结果为 c。元素 c 可以与元素 d 合并,结果为 e。
- VA[0] = {一个}
- VA[1] = {b, q}
- VA[2] = {d, r}
上例中的所有解都是:{a,b}, {a,d}, {b,d}, {a,b,d}。
任务是找到给定向量 VA 中的所有解。
我的 C++ 代码是:
void findAll(unsigned int step, unsigned int size, const T pUnifier, int hole_id) {
if(step == size) printOneResult(pUnifier);
else {
_path[step] = -1;
findAll(step + 1, pUnifier, step);
}
std::vector<T> vec = VA[step];
for(std::vector<T>::const_iterator it = vec.begin(); it < vec.end(); it++) {
T nextUnifier();
if( merge( *it, pUnifier, nextUnifier )) {
_path[lit_id] = it->getID();
findAll(step + 1, nextUnifier, hole_id);
}
}
}
代码包含递归调用;但是,它不是尾递归的。它在实践中运行缓慢。实际上,VA 的大小可能是数百,每个子向量的大小也可能是数百。我想知道它是否可以优化。
非常感谢。