
Comments and Discussions



Its name is next_combination. It computes the next combination based on the current combination. The code contract is the r must be a valid combination in the 1st place.





Thank you very much. It's nice code!





Respected Sir,
As per subject can you please give us the help so we can use your "Combinations in C++" for the array of float numbers.
Thanking you.
regards,
Deepak





You can convert the char array example of using next_combination to float array. next_combination works on iterators so it should work on array as well.





Thanks for your help and mail,sir. First I tried to run your example of char string i.e. n=123456 and r=1234 it runs fine, then I did what you said i.e. I did char [] as float [10] for n and r and then run in output it shows memory address for all pair (same value). Sir can you help me to solve this problem and second thing which I miss to mention in first mail is that I want to convert these code in ANSI C.
Thanking you.






Sir, Thanks for your help. Sir I just saw your part 2 upload, which is what I am looking for.I have implemented my algorithm in matlab which is serial now I want to convert it in c and parallel, and then test on cuda. so now I am understanding your "The Technique of Finding Combination, Given its Index" which you have explained very good, thanks. sir, I have not so far downloaded software and tested it, I will be very grateful to you if you help me to convert it in c language else I need to write my code in c++ which I don't know as I just started learning c language.
Thanking you.





For C language, you can try changing from
template <class BidIt>
bool next_combination(BidIt n_begin, BidIt n_end,
BidIt r_begin, BidIt r_end);
to
bool next_combination(float* n_begin, float* n_end,
float* r_begin, float* r_end);





Sir, as you said in "A Benchmark Program for your PC" that "The program does not store the combination anywhere and discards them after every computation". If we want to see the combinations after computations, what and where we need to do the change in "TimeCombinations". Thanking you.
Sir, I also not find the source folder for "The Technique for Finding Combinations Without Repetitions" for example "Find Combinations of 3 from a Sequence of 5" with "Optimised Version: Index Combination". sir I will be very grateful if you can send/give idea where can I get it. Thanking you.





It is in the IntComb folder of 1st source download. I suggest you concentrate on converting next_combination function to c language 1st because that is what you need.





Thank you sir,in said folder I found the example by replacing the animal names by integers, it also works for floating numbers. sir I now started working on C++, as I found that more peoples are using it than C.
sir I repeat my first question again here,
Sir, as you said in "A Benchmark Program for your PC" that "The program does not store the combination anywhere and discards them after every computation". If we want to see the combinations after computations, what and where we need to do the change in "TimeCombinations". Thanking you.
sir, can you give more idea on how your code in "TimeCombinations" finds number of processors in cpu (as in my case 4) and split to find for combination for "91". Sir can it be possible if we use one thread in GPU for each combination. Thanking you.





Sir, there is correction in my previous reply, the correction is that in "TimeCombination" we don't find combination for 91, so my question is,on how your code in "TimeCombinations" finds number of processors in cpu (as in my case 4) and split to find on each processor. Sir can it be possible if we use one thread in GPU for each combination. Thanking you.





Hi, you can keep the combinations for the benchmark by saving the vec variable in the IndividualThreadProc function of the TimeCombinationDlg.cpp.
You can find the 91 index example under the FindComb folder.
You cannot run the index code in the GPU because the GPU does not compute arbitrarysized integers.





Sir, thanks for your help and reply, sir sorry I do not understand the meaning of "GPU does not compute arbitrarysized integers." Sir, can you pls. help me to get the meaning by giving idea of this or tell me where can I get more info of this on net. Sir, does do you have any of your code of combinations for GPU or idea where can we find it. Thanking you.





Arbitrarysized integers means it can grow larger than 32bit or 64bit to hold a very large integer value. There is no library to compute combination on GPUs as far as I know. I have a way to compute combination on GPU but I have not written the code or the article.





Sir, thanks for info. Sir as you said you know the way to compute combination on GPU, can I request you to give few more idea of same, so it will help me to think of that. Thanking you.





Without going too much into details. Since GPU cannot use arbitrary sized integer, we have to resort to using the biggest integer that the combination need to use by calculating the largest factorial needed. Example, since 10! falls within range of the 32bit integer, there is no need to use a larger integer. If we need a integer larger than 64 bit, we have to define the type ourselves using CUDA PTX assembly to help us detect the carry bit.





sir,Thanks for help and info.This info help me in thinking on how can we do combination on GPU. Sir in one of my early reply I asked one question which I am writing here again " Sir can it be possible if we use one thread in GPU for each combination in "Timecombination" i.e. instead of using only number of processor in CPU. Thanking you.





The answer to your question is yes.





Sir, Thanks for help and reply, currently I am working on c++ and then I will work on your algo. Thanking you.





Respected Sir,
sir do you have used open MP or MPI in your code to do serial code execution on all cores in CPU.
Thanking you.






Sir, thanks for your reply.





for(long ab=0;ab<maxx*maxy;++ab){
long aa = ab / maxx;
long bb = ab % maxy;
if(aa<bb) {
}
}
modified 10May13 16:47pm.






#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
int nCk(int n,int loopno,int ini,int *a,int k)
{
if(k==0)
return 1;
static int count=0;
int i;
loopno;
if(loopno<0)
{
a[k1]=ini;
for(i=0;i<k;i++)
{
printf("%d,",a[i]);
}
printf("\n");
count++;
return 0;
}
for(i=ini;i<=nloopno1;i++)
{
a[k1loopno]=i+1;
nCk(n,loopno,i+1,a,k);
}
if(ini==0)
return count;
else
return 0;
}
void main()
{
int n,k,*a,count;
printf("Enter the value of n and k\n");
scanf("%d %d",&n,&k);
a=(int*)malloc(k*sizeof(int));
count=nCk(n,k,0,a,k);
printf("No of combinations=%d\n",count);
getch();
}
modified 20Jan12 14:41pm.






Hi Shao,
The article is very interesting. Actually, couple years ago, I have written my own algorithms for calculating Combinations, Permutations and Factorial in C# using iterative approach rather than recursive for performance reason: iterative solutions in many cases provides several order of magnitude better performance than recursive ones. Corresponding online Combinatorics Calculator, powered by these algorithms, is available at: http://www.webinfocentral.com/MATH/Combinatorics.aspx[^]
Good job! 5*
Best regards,
Alex





Dear Wong Shao Voon, dear all,
I used succesfully your code "prev_comb_ex.cpp" for finding all combinations  thanks!
(BTW: next_comb_ex.cpp unfortunately has some compile error as unzipped, which I could not yet fix.)
Of course directly possible to get e.g. all pairs out of all(, when using r=2).
Anyhow, I need to find all combinations of exactly two pairs out of all,
means e.g.:
all={1,2,3,4} => { (1,2),(3,4); (1,3),(2,4); (1,4),(2,3) }
It seems that your code should easily be adoptable/appliable for such prblem as well,
but I am not able to see how / get it ...
Any idea, help, already solved this (similar) problem?
Thanks a lot!
Frank





Hi Frank,
It doesn't seem like combinations to me from your description. Looks more like finding the all permutations, then split the each permutation into tuples of 2.





Hi,
I saw the old posts about this issue, but I haven't seen the solution.
I also need the combination of vector elements for unlimited number of vectors. I'm running out of time and you might have coded it already, so I don't have to brainstorm with it..
If you do, I'd really appreciate your help.
Also I'm not really into this topic, need some time to get familiar with.
Thanks.





Here is a FindVecComb() function and example code to do it. I hope this is what you want.
#include <windows.h> #include <vector> #include <string> #include "combination.h"
template<class T> bool FindVecComb( std::vector< std::vector< T > >& VecN, std::vector< std::vector< T > >& VecR );
int _tmain(int argc, _TCHAR* argv[]) { using namespace std; typedef vector<char> Set;
vector<Set> VecOrig;
Set v1, v2, v3; v1.push_back('A'); v1.push_back('B'); v1.push_back('C'); v1.push_back('D'); v2.push_back('A'); v2.push_back('B'); v2.push_back('C'); v3.push_back('A'); v3.push_back('B'); v3.push_back('C'); VecOrig.push_back(v1); VecOrig.push_back(v2); VecOrig.push_back(v3);
vector<Set> VecResults;
VecResults.push_back( Set() ); VecResults.push_back( Set() ); VecResults.push_back( Set() );
VecResults.at(0).push_back( v1.at(0) ); VecResults.at(0).push_back( v1.at(1) ); VecResults.at(0).push_back( v1.at(2) ); VecResults.at(1).push_back( v2.at(0) ); VecResults.at(1).push_back( v2.at(1) ); VecResults.at(2).push_back( v2.at(0) ); VecResults.at(2).push_back( v2.at(1) );
while(FindVecComb( VecOrig, VecResults ) ) { std::string str=""; for( size_t i=0; i<VecResults.size(); ++i ) { for( size_t j=0; j<VecResults.at(i).size(); ++j ) { str+=VecResults.at(i).at(j); } str+="  "; } str+="\n"; OutputDebugStringA(str.c_str()); }
return 0; }
template<class T> bool FindVecComb( std::vector< std::vector< T > >& VecN, std::vector< std::vector< T > >& VecR ) { if(VecR.size() == 0) return false;
size_t nDepth = VecR.size()1; bool NoMore = true; do { NoMore = stdcomb::next_combination( VecN.at(nDepth).begin(), VecN.at(nDepth).end(), VecR.at(nDepth).begin(), VecR.at(nDepth).end() );
if(NoMore == false) { // Initailize as before for( size_t i=0; i<VecR.at(nDepth).size(); ++i) { VecR.at(nDepth).at(i) = VecN.at(nDepth).at(i); } }
if( nDepth == 0 && NoMore == false) return false;
nDepth; } while(NoMore == false);
return true; }
Have a nice day!





Yes it is. Thank you.
Though I found out that one combination is missing from the results.
It gives:
ABCD  AB  AC 
ABCD  AB  BC 
ABCD  AC  AB 
ABCD  AC  AC 
ABCD  AC  BC 
ABCD  BC  AB 
ABCD  BC  AC 
ABCD  BC  BC 
The first one should be ABCD  AB  AB .
I tested no matter what you change in the sets the very first combination is always missing.
I'm looking for the bug. If you have an idea please let me know!
Also I'm trying to use it with vector , but FindVecComb returns false...
Did you tested the code with CString as element of the vector?
Thanks.
modified on Tuesday, June 10, 2008 3:08 AM





It doesn't gives you the first combination because the first combination is what you feed into the function to get the next combination and subsequently the rest of the combinations. Therefore you already have the first combination.
You cannot use a vector because you cannot compare a vector with another vector, unless you write a vector comparison function or functor.
I have not tested with CString but it should work with CStrings because CStrings are comparable.





I got it working.
Thanks!





First of all, I really like your article.
There is a question. As we know, any permutation has signature, i. e. 
1,2,3  signature is 1.
2,1,3  signature is 1.
Have you ever tried to write next_permutation() like this:
int next_permutation(/*arguments*/)  returns 0 if sequence is sorted, e.g.  1,2,3; otherwise returns the signature (1 or 1) of the current permutation?
This would be really usefull. For example, in matrix determinant calculation.





Hi Alexander,
Thanks for your compliments. As for your question, I'll look into it.
Best regards,
Wong Shao Voon





Hi Alex, under the section "Code Examples for Finding Index from Permutation" of this article: Permutations in C++, Part 2[^], it is written in response to your question. I hope it is what you are looking for!





Hi Again,
I tried your solution and it worked except for one thing. I wanted not to use
"const int N_NUM and const int R_NUM". My idea to input these value at will, but because the compiler is expecting a constant expression, it doesn't compile. Below is something I tried that didn't work. I am showing to give an int of what I want to do.
int a=0, b=0;
cout<<"input a: "<<endl;
cin>>a;
cout<<"input b: "<<endl;
cin>>b;
int *N_NUM;
int *R_NUM;
N_NUM = new int a;
R_NUM = new int b;
Thanks.........





Hi computerpublic,
I declared them as const because to declare the n[] array and r[] array on the stack requires a constant number to tell the compiler how big is the array. If N_NUM and R_NUM is not const, then you have to allocate your arrays dynamically using 'new' but you also must remember to delete them away after use. Allocate your arrays dynamically is good if you do not know how big is your array until the user runs your program.
Below is the edited main() code,
Best regards, Wong Shao Voon
<code> #include <iostream>
using namespace std;
void char_combination(int n[],int n_column,int r[], int r_size, int r_column, int loop);
int main() { int N_NUM=10; int R_NUM=5; int* pn= new int[N_NUM];
if( 0 == pn ) { cout<<"Failed to allocate memory"<<endl; return 1; }
// initialize the n array pn[0]=1; pn[1]=2; pn[2]=3; pn[3]=4; pn[4]=5; pn[5]=6; pn[6]=7; pn[7]=8; pn[8]=9; pn[9]=0; int* pr= new int[R_NUM];//+1 for the NULL character if( 0 == pr ) { delete [] pn; cout<<"Failed to allocate memory"<<endl; return 1; } // initialize the r array pr[0]=1; pr[1]=2; pr[2]=3; pr[3]=4; pr[4]=5;
char_combination(pn,0,pr,R_NUM,0,N_NUMR_NUM);
cout<<"Complete!"<<endl;
delete [] pn; delete [] pr;
system("pause");
return 0; }
void char_combination(int n[],int n_column,int r[], int r_size, int r_column, int loop) { int localloop=loop; int local_n_column=n_column;
///////Display the string code///////// if(r_column>(r_size1)) { for( int i=0; i<r_size; ++i ) cout<<r[i];
cout<<endl; return; } /////End of displaying string code//////
for(int i=0;i<=loop;++i) { r[r_column]=n[n_column+i]; ++local_n_column; char_combination(n,local_n_column,r,r_size,r_column+1,localloop); localloop; } } </code>





This really doesn't work for me and I could tell just by looking at it. I ran it to confirm my thoughts and it doesn't work. My objecting is to input all the following without having to explicitly say what they are and what size the array is going to be:
const int N_NUM=10;
const int R_NUM=4;
int n[]={1,3,6,8,15,17,20,21,39,40};
The solution you provided is explicitly detailing the size of the array and this cannot work for me. Thanks for your help thus. I wish I was so talented.
Bye.





Hi computerpublic,
You can use std::vector and stdcomb::next_combination() if you do not know how big is your array and what numbers they will contain.
Best regards,
Wong Shao Voon





i don't understand how to use this method.





All I want to do is to not use the "const" expression so I can do my inputs from the terminal. Is there no simpler way to do this????





I already told you that you can use std::vector and stdcomb::next_combination(): whenever the user enters a number, you just push back the number into the n vector and before you call next_combination() for the first time, initialise the r vector.





You can look at next_comb_ex.cpp in the source files for examples on how to use next_combination().
Below is one of the examples,
template
void display(BidIt begin,BidIt end)
{
for (BidIt it=begin;it!=end;++it)
cout<<*it<<" ";
cout<<endl;
}
using namespace std;
using namespace stdcomb;
//test next_combination() with iterators
int main()
{
vector ca;
ca.push_back (1);
ca.push_back (2);
ca.push_back (3);
ca.push_back (4);
ca.push_back (5);
ca.push_back (6);
vector cb;
cb.push_back (1);
cb.push_back (2);
cb.push_back (3);
cb.push_back (4);
do
{
display(cb.begin(),cb.end());
}
while(next_combination(ca.begin (),ca.end (),cb.begin (),cb.end()) );
cout<<"Complete!"<<endl;
return 0;
}





Hello,
I modified the combinaton code to use numbers instead of letters. It compils and builds successfully. However, the output seems like just a vector address. Can you please tell me what I am doing wrong.
Thanks.
//char_comb_ex.cpp
//This program finds combinations using the recursive method
/*****Instructions*******
To see how it works for other combinations
Try setting N_NUM to other numbers (must not be greater than 10)
Try setting R_NUM to other numbers (must not be greater than N_NUM)
*************************/
#include
using namespace std;
//function prototype
//void char_combination(char n[],int n_column,char r[], int r_size, int r_column, int loop);
void char_combination(int n[],int n_column,int r[], int r_size, int r_column, int loop);
int main()
{
const int N_NUM=10;
const int R_NUM=5;
int n[]={1,2,3,4,5,6,7,8,9,0};
int r[R_NUM+1];//+1 for the NULL character
r[R_NUM]='\0';
char_combination(n,0,r,R_NUM,0,N_NUMR_NUM);
cout<<"Complete!"<<endl;
return 0;
}
void char_combination(int n[],int n_column,int r[], int r_size, int r_column, int loop)
{
int localloop=loop;
int local_n_column=n_column;
///////Display the string code/////////
if(r_column>(r_size1))
{
cout<<r<<endl;
return;
}
/////End of displaying string code//////
for(int i=0;i<=loop;++i)
{
r[r_column]=n[n_column+i];
++local_n_column;
char_combination(n,local_n_column,r,r_size,r_column+1,localloop);
localloop;
}
}





Hi computerpublic, you have to change the display code for displaying individual integer as it is for a char array. Below is the modified char_combination code.
void char_combination(int n[],int n_column,int r[], int r_size, int r_column, int loop);
int main() { const int N_NUM=10; const int R_NUM=5; int n[]={1,2,3,4,5,6,7,8,9,0};
int r[R_NUM+1];//+1 for the NULL character r[R_NUM]='\0';
char_combination(n,0,r,R_NUM,0,N_NUMR_NUM);
cout<<"Complete!"<<endl; return 0; }
void char_combination(int n[],int n_column,int r[], int r_size, int r_column, int loop) { int localloop=loop; int local_n_column=n_column;
///////Display the string code///////// if(r_column>(r_size1)) { for( int i=0; i<r_size; ++i ) cout<<r[i];
cout<<endl; return; } /////End of displaying string code//////
for(int i=0;i<=loop;++i) { r[r_column]=n[n_column+i]; ++local_n_column; char_combination(n,local_n_column,r,r_size,r_column+1,localloop); localloop; } }





Thank you very much. I will try the new solution.





I would like to generate all possible combinations using a sequence of vectors, where each vector contains all items that are allowed to stand at a certain place of the combination. For example, from the following input:
{ A } { A, B, C } { C } { D } { E, F }
I would like to get the following 5item combinations:
AACDE
AACDF
ABCDE
ABCDF
ACCDE
ACCDF
I use std::vector<std::vector<ITEM>> to represent the input, where ITEM is a class representing A , B , C , D , E or F . The result should also come as std::vector<std::vector<ITEM>> .
It looks like I might achieve the above result using your algorithm, but does it support variable counts/sets of allowed items at individual positions?







General News Suggestion Question Bug Answer Joke Rant Admin Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

