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
tspj20
- 4 Contributors
- forum3 Replies
- 4 Views
- 10 Years Discussion Span
- comment Latest Post by ArkM
Salem 5,138
Use the STL perhaps?
http://www.sgi.com/tech/stl/next_permutation.html
Unless of course using recursion is actually your homework assignment.
findsyntax -6
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 1,090
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.