Take the 2-minute tour ×

Assume there is a vector VA of size N, and each element is another vector of type T. There is an operation on type T and returning a new value of type T, i.e., bool merge(T a, T b, T &ret);. If a and c can be merged, then store the result in ret and return true; otherwise, return false. The merge operation is reflective and transitive.

A solution is found if either:

  1. ∃ x0, x1, ..., xN-1. merge(VA[0][x0], VA[1][x1], merge(VA[2][x2], ..., merge(VA[N-2][xN-2],VA[N-1][xN-1], ret)...));
  2. any elements from N-1 (not N) sub-vectors can be merged (pick any N-1 with exactly one exception).

For example: VA is of size 3. Element a can be merged with Element b with the result c. Element c can be merged with Element d with the result e.

  • VA[0] = {a}
  • VA[1] = {b, q}
  • VA[2] = {d, r}

All solutions in the above example are: {a,b}, {a,d}, {b,d}, {a,b,d}.

The task is to find all solution in the given vector VA.

My C++ code is:

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);

The code contains recursive calls; however, it is not tail recursive. It is running slowly in practice. In reality, the size of VA is possibly hundreds and each sub-vector size is of hundreds, too. I'm wondering whether it can be optimized.

Thank you very much.

share|improve this question
C++ won't optimize your tail recursive calls (at least not according to the standard) so that's a minor concern. Have you looked in your for loop? I imagine that's where most of the time is spent because your iterations can stack up. You're looping and recursing into possibly another loop with recursion, ad infinitum. If you could cut down on some of the looping, that could net you a big gain in cycles saved. Not saying it's possible (I haven't looked at it closely enough), but it's worth researching. –  RonaldBarzell Dec 22 '12 at 0:09
Thank you for your reply. It is hard to cut down some looping. It depends on ordering, but it is hard to find a good sorting heuristic. Maybe, I can consider how to memorize some partial results. –  Tianyi Liang Dec 22 '12 at 0:27
You could also see if there's anything you can do to your data before it goes into the findAll so that you can take some shortcuts. –  RonaldBarzell Dec 22 '12 at 0:31
Is your return type bool or void? It can't be both, and if it's the former, you're missing a return statement. –  ildjarn Dec 22 '12 at 1:28
Sorry, for the recursive function, the return type is void. I just remove the ambiguity. –  Tianyi Liang Dec 22 '12 at 2:23

2 Answers 2

If I'm understanding your code correctly, you're performing a (recursive) brute-force search. This is not efficient, since you're given some information about your search space.

I think a good candidate here would be the A* algorithm. You could use the current greatest-chain size as the heuristic, or perhaps even the sum of the squares of the chain sizes.

share|improve this answer
it is really hard to prune the search space, and in fact almost every search path is useful. Therefore, I'm thinking to optimize the recursive structure itself. –  Tianyi Liang Dec 29 '12 at 5:34

To improve your code, as you use vectors, you should use the [] operator, with a int counter instead of simple iterators, that are much much slower. You can improve it even more by minimising the function calls i either of your loops, like previously stacking the values you will use. Since you didn't explained what really was a T_VEC, i coudln't not wrote the complete iterator-free version, but this should already be a great plus regarding speed.

share|improve this answer
-1 In release builds you would be extremely hard-pressed to find a modern standard library implementation whose std::vector<> iterators have any overhead whatsoever. –  ildjarn Dec 22 '12 at 1:15
Based on what evidence? Last I checked, iterators had a slight edge over indexing... –  GManNickG Dec 22 '12 at 1:16
For clearance, T_VEC is std::vector<T>, T is some complicated data structure(just consider it as a template). It is better to use a iterator than an int counter. Based on my previous testing, I don't see any speedup by using an int counter, on the other side, an iterator is more convenient. –  Tianyi Liang Dec 22 '12 at 2:21
Well, it's true that the difference between iterators and index access speed depends on the compiler and optimisations, my bad here. But you can at least reduce execution time by removing useless calls to vec.end() by saving it in another iterator and comparing them. If the loop is large, it should be significant. –  tsukasan Dec 22 '12 at 2:35
@tsukasan No, I don't think so. vec.end() returns an address, just like an int. The overhead is too small. You may try a loop for a million times. There will not be any difference. –  Tianyi Liang Dec 22 '12 at 2:43

Your Answer


