problem with recursion

[tspj20]

I have an arbitary vector where I have to try all combinations (sum up different combinations) of elements within the vector. I want to use recursion for this but I have trouble in coding that. I have tried something similar but with a fixed vector size, using for loops. But in this case I cant really use for loops because the vector size can change randomly. How do I integrate this into a recursive algorithm?
Thanks

[Salem]

Use the STL perhaps?
http://www.sgi.com/tech/stl/next_permutation.html

Unless of course using recursion is actually your homework assignment.

[findsyntax]

Hi,
I am Rammohan from Bangalore and working as a Technical lead in big IT firm .
Solution for your answer is follows:

Let’s suppose you have a set of N elements in a vector and want to find all the combinations of size M (M > 0 and M <= N). Start by taking one element as the first one. Then, find a second element to the right of the first one, then a third element to the right of the second one, etc. Follow this method until you’ve chosen M elements.
Example with elements (a, b, c), finding the combinations of two elements. The first one can be a, b or c. If it’s a, the second one can be b or c (for combinations ab and ac). If it’s b, the second one can only be c (forming bc) and if the first one is c there are no elements to its right to choose a second element. Hence, the combinations are ab, ac and bc. This isn’t rocket science.
Any algorithm that performs this task will be valid. Mine’s recursive, because I consider it easier this way. You have to search elements to the right of the previous one, and have to perform this task with M depth, so I think it calls for a recursive algorithm. Every recursive algorithm can be algorithmically transformed into an iterative algorithm, so feel free to do the conversion if you’re an iteration fan.
My test program has a recursive function, a wrapper function to simplify doing the initial call, and a main program that tests the algorithm by extracting the combinations of 3 elements out of 5. I can mail you the full programs on request, as usual. I will paste only the recursive function. First the code, then the explanation:

void combinations_recursive(
  const vector<char> &elems,
  unsigned long req_len,
  vector<unsigned long> &pos,
  unsigned long depth,
  unsigned long margin
)
{
  // Have we selected the requested number of elements?
  if (depth >= req_len) {
    for (unsigned long ii = 0; ii < pos.size(); ++ii)
      cout << elems[pos[ii]];
    cout << endl;
    return;
  }

  // Are there enough remaining elements to be selected?
  // This test isn't required for the function to be
  // correct, but it saves futile calls.
  if ((elems.size() - margin) < (req_len - depth))
    return;

  // Try to select new elements to the right of the last
  // selected one.
  for (unsigned long ii = margin; ii < elems.size(); ++ii) {
    pos[depth] = ii;
    combinations_recursive(elems, req_len, pos, depth + 1, ii + 1);
  }
  return;
}

Regards,
Rammohan Alampally,
<snip false signature>

[ArkM]

Yet another solution:

/** This wrapper class is a slightly adapted solution from:
 * http://www.cut-the-knot.org/do_you_know/AllPerm.shtml
 */
template <class T> class Visiter
{
public:
    Visiter(const T& v):vref(v),Value(v.size(),-1),level(-1)
    {
        visit(0);
    }
    virtual ~Visiter() {}
private:
    const T& vref;
    int level;
    std::vector<int> Value;
    
    void visit(int k)
    {
      Value[k] = level;
      level = level + 1;
      if (level == N)
        AddItem();
      else
        for (int i = 0; i < N; i++)
          if (Value[i] < 0)
            visit(i);
      level = level-1; Value[k] = -1;
    }

    virtual void AddItem()
    {
        for (int i = 0; i < N; ++i)
            std::cout << " " << vref[Value[i]];
        std::cout << std::endl;
      // Form a string from Value[0], Value[1], ... Value[N-1].
      // At this point, this array contains one complete permutation.
      // The string is added to the list box for display.
      // The function, as such, is inessential to the algorithms.
    }
};
/// It seems a function template is more convenient...
template <class T>
void AllPermutations(const T& v)
{
    Visiter<T> doit(v); // I find it funny, don't you?..
}
/// Test for vector<int> and vector<string>
int main(int argc, char* argv[])
{
    std::vector<int> vints;

    vints.push_back(1);
    vints.push_back(2);
    vints.push_back(3);
    AllPermutations(vints);

    std::vector<std::string> names;

    names.push_back("Helen");
    names.push_back("Mary");
    names.push_back("Ann");
    AllPermutations(names);

    return 0;
}

Apropos, look at http://www.cut-the-knot.org/do_you_know/AllPerm.shtml.