recursion in combinations

[Gary Wessle]

Hi

I came up with this code which prints out all combinations as in
"c_choose_k"
so, if we have a vector of char abcdef, and we want all combinations
with 3 elements only, we make the 3 for loops as below,
int main(){
vector<string> s;
s.push_back("1");
s.push_back("2");
s.push_back("3");
s.push_back("4");
s.push_back("5");
s.push_back("6");

for(unsigned p=0; p<s.size(); p++){
for(unsigned q=p+1; q<s.size(); q++)
for(unsigned r=q+1; r<s.size(); r++)
cout << s[p]
<< s[q]
<< s[r]
<< endl;
}
}

I am thinking to generalize it and make it more flexible, so that it
takes n and k and puts out a vector<vector<int> > each vector<int>
contains the combined elements and the main vector contains all the
combination vectors.
i.e
n = 3
k = 2
vector<int>.size() == k "2 in this case"
vector<vector<int> > .size() == n_choose_k "3" in this case
here, 3 is the number of combinations, and 2 is the number of digits
in each of the "k"
12
13
23


n = 6
k = 3
vector<int>.size() == k "3 in this case"
vector<vector<int> > .size() == n_choose_k "20 in this case"
so that the vector of vector looks like
123
124
125
126
134
135
136
145
146
156
234
235
236
245
246
256
345
346
356
456

so instead of feeding a vector of values to the routine, I can just
use the first argument "n" as an index representation of the number of
elements need to be combined, then use this index to get the element
combination in the client code.

I tried to do it recursively but need some help. I was thinking

vector<vector<int>> n_choose_k(int n, int k){
static int nn = n;
vector<int> vk;
vector<vector<int>> vn;
int a = nn==n ? 0 : n+1;
for(int i=a; i<n; i++)
unsigned kk -= k;
ok, I am just scratching my head here...
vector.push_back(something) some where .. i give up


thanks

 

[ashani]

Can you take a look at the code snippet pasted below:

////////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

typedef std::vector<std::vector<int> >::iterator ITER;

void GetResults(int n,
int k,
int start,
std::vector<std::vector<int> > &results
)
{

if (k == 1)
{
for (int i = start; i <= n; i++)
{
std::vector<int> tmp;
tmp.push_back(i);
results.push_back(tmp);
}
return;
}

for (int i = start; i <= n; ++i)
{

std::vector<std::vector<int> > tmp;
GetResults(n, k-1, i+1, tmp);

ITER iterEnd = tmp.end();
for (ITER iter = tmp.begin(); iter != iterEnd; ++iter)
{
std::vector<int> vSeq;
vSeq.push_back(i);

std::copy(iter->begin(), iter->end(), std::back_inserter(vSeq));
results.push_back(vSeq);
}
}
}

std::vector<std::vector<int> > N_Choose_K(int n, int k)
{
std::vector<std::vector<int> > vResult;
if (k > 0 && k <= n)
{
GetResults(n, k, 1, vResult);
}
return vResult;
}

int main()
{
std::vector<std::vector<int> > vResults = N_Choose_K(6, 3);

ITER iterEnd = vResults.end();
for (ITER iter = vResults.begin(); iter != iterEnd; ++iter)
{
std::copy(iter->begin(), iter->end(),
std:stream_iterator<int>(std::cout, " "));
std::cout << std::endl;
}
std::cout << "Count = " << vResults.size() << std::endl;
return 0;
}
///////////////////////////////////////////////////////////////////////

 

[defendusa2]

Is this a homework assignment?

------------------------------------------------
Bumperstickers: http://www.cafepress.com/bush_doggers?pid=2794571

Hi

I came up with this code which prints out all combinations as in
"c_choose_k"
so, if we have a vector of char abcdef, and we want all combinations
with 3 elements only, we make the 3 for loops as below,
int main(){
vector<string> s;
s.push_back("1");
s.push_back("2");
s.push_back("3");
s.push_back("4");
s.push_back("5");
s.push_back("6");

for(unsigned p=0; p<s.size(); p++){
for(unsigned q=p+1; q<s.size(); q++)
for(unsigned r=q+1; r<s.size(); r++)
cout << s[p]
<< s[q]
<< s[r]
<< endl;
}
}

I am thinking to generalize it and make it more flexible, so that it
takes n and k and puts out a vector<vector<int> > each vector<int>
contains the combined elements and the main vector contains all the
combination vectors.
i.e
n = 3
k = 2
vector<int>.size() == k "2 in this case"
vector<vector<int> > .size() == n_choose_k "3" in this case
here, 3 is the number of combinations, and 2 is the number of digits
in each of the "k"
12
13
23


n = 6
k = 3
vector<int>.size() == k "3 in this case"
vector<vector<int> > .size() == n_choose_k "20 in this case"
so that the vector of vector looks like
123
124
125
126
134
135
136
145
146
156
234
235
236
245
246
256
345
346
356
456

so instead of feeding a vector of values to the routine, I can just
use the first argument "n" as an index representation of the number of
elements need to be combined, then use this index to get the element
combination in the client code.

I tried to do it recursively but need some help. I was thinking

vector<vector<int>> n_choose_k(int n, int k){
static int nn = n;
vector<int> vk;
vector<vector<int>> vn;
int a = nn==n ? 0 : n+1;
for(int i=a; i<n; i++)
unsigned kk -= k;
ok, I am just scratching my head here...
vector.push_back(something) some where .. i give up


thanks

 

[Gary Wessle]

Is this a homework assignment?

No, it is NOT a homework assignment.

 

[Mark P]

Hi

I came up with this code which prints out all combinations as in
"c_choose_k"
so, if we have a vector of char abcdef, and we want all combinations
with 3 elements only, we make the 3 for loops as below,

[snip]

There are easier way to do this. One option is to take advantage of the
standard library function next_permutation defined in the standard
header <algorithm>. Start with a "mask" vector such as:

0 0 0 0 0 1 1 1

Repeatedly apply next_permutation to this vector until the function
returns false. For each mask, including the first, pick out the
elements of the input vector that correspond to a '1' in the mask.

The example above gives 8C3, by changing the length of the mask (n) and
the number of ones (m), you can get nCm.

Mark

 

[Victor Bazarov]

[snip]

There are easier way to do this. One option is to take advantage of
the standard library function next_permutation defined in the standard
header <algorithm>. Start with a "mask" vector such as:

0 0 0 0 0 1 1 1

Repeatedly apply next_permutation to this vector until the function
returns false. For each mask, including the first, pick out the
elements of the input vector that correspond to a '1' in the mask.

The example above gives 8C3, by changing the length of the mask (n)
and the number of ones (m), you can get nCm.

I think this would give repeated patterns. For example, swapping the
last 1 with the one-before-last 1 is a different permutation (of this
vector), but not a different combination.

V

 

[Mark P]

[snip]

There are easier way to do this. One option is to take advantage of
the standard library function next_permutation defined in the standard
header <algorithm>. Start with a "mask" vector such as:

0 0 0 0 0 1 1 1

Repeatedly apply next_permutation to this vector until the function
returns false. For each mask, including the first, pick out the
elements of the input vector that correspond to a '1' in the mask.

The example above gives 8C3, by changing the length of the mask (n)
and the number of ones (m), you can get nCm.

I think this would give repeated patterns. For example, swapping the
last 1 with the one-before-last 1 is a different permutation (of this
vector), but not a different combination.

V

Not so. next_permutation will yield a lexicographically greater
ordering of the input sequence if one exists, or return false if none
exists. If you think about it for a minute, I think you'll see that it
must behave in this way, otherwise it would have no way to keep track of
its "position". That is, how can it know whether it's at the first
occurrence of 0 1 1 or the second such occurrence, given that the input
is merely a pair of iterators?

// Example: prints the 10 permutations of {0,0,1,1,1}

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

using namespace std;

int main ()
{
int data[] = {0,0,1,1,1};
vector<int> data_vec( data, data + sizeof(data)/sizeof(data[0]));

do
{
copy( data_vec.begin(), data_vec.end(),
ostream_iterator< int>( cout, " "));
cout << endl;
}
while( next_permutation( data_vec.begin(), data_vec.end()));
}

-Mark

 

[Victor Bazarov]

[snip]

There are easier way to do this. One option is to take advantage of
the standard library function next_permutation defined in the
standard header <algorithm>. Start with a "mask" vector such as:

0 0 0 0 0 1 1 1

Repeatedly apply next_permutation to this vector until the function
returns false. For each mask, including the first, pick out the
elements of the input vector that correspond to a '1' in the mask.

The example above gives 8C3, by changing the length of the mask (n)
and the number of ones (m), you can get nCm.

I think this would give repeated patterns. For example, swapping the
last 1 with the one-before-last 1 is a different permutation (of this
vector), but not a different combination.

V

Not so. next_permutation will yield a lexicographically greater
ordering of the input sequence if one exists, or return false if none
exists. [..]

My bad. For some reason (incorrectly) I thought (what was I thinking?)
that next_permutation doesn't depend on the sequence...

V