0

Thanks

Not Yet Answered # problem with recursion

Salem 5,138 findsyntax -6 ArkM 1,090 OK, so HostGator for some reason no longer allows gcc/g++ access unless you have a Designated Server account, which is a lot of money to spend just to compile my "Hello World" program. Thus I figured I'd compile at home, then upload. Program is your regular old bare-bones Hello World ...

0

Thanks

0

Use the STL perhaps?

http://www.sgi.com/tech/stl/next_permutation.html

Unless of course using recursion is actually your homework assignment.

0

Hi,

I am * Rammohan *from Bangalore and working as a

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>

0

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.

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

I don’t want at this stage work on a big separate project as I've already got plenty ...

Hi. I have a form with list box : lst_product, datagridview : grd_order and button: btn_addline. lst_product has a list of product ids selected from database (MS Acess 2013) , grd_order is by default empty except for 2 headers and btn_addline adds rows to grd_order.

btn_addline :

`Private Sub btn_addline_Click(ByVal ...`