468,504 Members | 1,992 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,504 developers. It's quick & easy.

recursion in combinations

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,
>>>>>>>>>>>>>>>code <<<<<<<<<<<<<<<<
int main(){
vector<strings;
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<intvk;
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
Aug 30 '06 #1
7 6865
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<inttmp;
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<intvSeq;
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::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
}
std::cout << "Count = " << vResults.size() << std::endl;
return 0;
}
///////////////////////////////////////////////////////////////////////

Aug 30 '06 #2
Is this a homework assignment?

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

Gary Wessle wrote:
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,
>>>>>>>>>>>>>>code <<<<<<<<<<<<<<<<
int main(){
vector<strings;
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<intvk;
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
Aug 30 '06 #3
de********@yahoo.com writes:
Is this a homework assignment?

No, it is NOT a homework assignment.
Aug 31 '06 #4
Gary Wessle wrote:
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
Aug 31 '06 #5
Mark P wrote:
[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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Aug 31 '06 #6
Victor Bazarov wrote:
Mark P wrote:
>[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<intdata_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
Aug 31 '06 #7
Mark P wrote:
Victor Bazarov wrote:
>Mark P wrote:
>>[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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Sep 1 '06 #8

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

5 posts views Thread by Peri | last post: by
20 posts views Thread by drs | last post: by
12 posts views Thread by da Vinci | last post: by
36 posts views Thread by rbt | last post: by
43 posts views Thread by Lorenzo Villari | last post: by
75 posts views Thread by Sathyaish | last post: by
18 posts views Thread by MTD | last post: by
20 posts views Thread by athar.mirchi | last post: by
35 posts views Thread by Muzammil | last post: by
reply views Thread by NPC403 | last post: by
3 posts views Thread by gieforce | last post: by
reply views Thread by fmendoza | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.