Add your own alternative version
Stats
240.1K views 5.3K downloads 68 bookmarked
Posted
12 Apr 2016

Comments and Discussions



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 <cstring>, 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<class BidIt><br />
void display(BidIt begin,BidIt end)<br />
{<br />
for (BidIt it=begin;it!=end;++it)<br />
cout<<*it<<" ";<br />
cout<<endl;<br />
}<br />
<br />
using namespace std;<br />
using namespace stdcomb;<br />
<br />
int main()<br />
{<br />
vector<int> ca;<br />
ca.push_back (1);<br />
ca.push_back (2);<br />
ca.push_back (3);<br />
ca.push_back (4);<br />
ca.push_back (5);<br />
ca.push_back (6);<br />
vector<int> cb;<br />
cb.push_back (1);<br />
cb.push_back (2);<br />
cb.push_back (3);<br />
cb.push_back (4);<br />
<br />
do<br />
{<br />
display(cb.begin(),cb.end());<br />
}<br />
while(next_combination(ca.begin (),ca.end (),cb.begin (),cb.end()) );<br />
<br />
cout<<"Complete!"<<endl;<br />
<br />
return 0;<br />
}





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<iostream>
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<br />
AACDF<br />
ABCDE<br />
ABCDF<br />
ACCDE<br />
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?





Dear Bartosz,
My implementation of next_combination does not support what you are going to do. However you can use next_combination to achieve what you want. Below is a sample code.
<pre>vector< vector<item> > VecOrig;<br />
<br />
// Must be initialise properly<br />
vector< vector<item> > VecResults;<br />
<br />
bool More = true;<br />
while( More )<br />
{<br />
More = false;<br />
for( int i=0; i<VecOrig.size(); ++i )<br />
{<br />
More = next_combination( <br />
VecOrig.at(i).begin(), VecOrig.at(i).end(), <br />
VecResults.at(i).begin(), VecResults.at(i).end() );<br />
}<br />
// print out your results for this round<br />
}<br />
</pre>
PS Please be noted that I did not test the code above.
Best Regards,
Shao Voon
Edited: some formatting





Hello Shao Voon,
I added the above (slightly modified) to your sample program, but the code crashes. Could you please take a look at the modified file at http://bartoszbien.com/TestCombo.cpp[^] ?
I included a comment inside the code. I believe that the output vectors have been allocated properly. Thank you.





Dear Bartosz,
Here is the modified code below. Right now, the code can only handle 2 input vectors. If you need me to write code which can handle any number of input vectors (which is nontrivial to write), please let me know.
using namespace std;
typedef vector<char> Set;
vector<Set> VecOrig;
Set v1, v2;
v1.push_back('A');
v1.push_back('B');
v2.push_back('C');
v2.push_back('D');
v2.push_back('E');
VecOrig.push_back(v1);
VecOrig.push_back(v2);
vector<Set> VecResults;
VecResults.push_back( Set() );
VecResults.push_back( Set() );
VecResults.at(0).push_back( v1.at(0) );
VecResults.at(1).push_back( v2.at(0) );
CString szResults;
bool More = true;
do
{
VecResults.at(1).at(0) = v2.at(0);
szResults += "{ ";
szResults += VecResults.at(0).at(0);
szResults += " ";
szResults += VecResults.at(1).at(0);
szResults += " }\n";
More = false;
do
{
More = stdcomb::next_combination(
VecOrig.at(1).begin(), VecOrig.at(1).end(),
VecResults.at(1).begin(), VecResults.at(1).end() );
if( More )
{
szResults += "{ ";
szResults += VecResults.at(0).at(0);
szResults += " ";
szResults += VecResults.at(1).at(0);
szResults += " }\n";
}
}
while( More );
More = stdcomb::next_combination(
VecOrig.at(0).begin(), VecOrig.at(0).end(),
VecResults.at(0).begin(), VecResults.at(0).end() );
}
while( More );
MessageBox( szResults );
/// I expect VecResults to be: { { A C } { A D } { A E } { B C } { B D } { B E } }





Hello,
Thank you for your effort. In my application, I need virtually unlimited number of sets; perhaps a recurrence could be the way?





Hi
Firstly thanks for the article.
When running next_comb_ex.cpp in VS2005 (VC++ 8), I get a crash debug assertion when
the code gets runs next_combination in combination.h. It's bombing out at this line:
tmp_r_begin; as the code tries to (via the prefix) go 1 BEFORE the first element of the iterator.
Given the context of this line ie.
BidIt tmp_r_begin=r_begin;<br />
tmp_r_begin;
why would this be correct coding ie. why would we go backwards from first iterator element?
For the PoD plain array version no crash, but I do note the same thing at the code line:
temp_r_being
we are setting the address to one BEFORE the first element of the array. Isn't this dangerous (well not dangerous I guess  it's only a pointer) as we don't actually know what could be stored there?
Thanks
 modified at 19:42 Sunday 6th August, 2006





Hi Petey Boy,
For the code below, tmp_r_begin is equivalent to vector::rend(). I have to do that because I have to use != instead of >= to be compliant with the STL and its iterators. I did not dereference anything at tmp_r_begin, so I thought that should be fine. Looks like that is not true for VC8.
<br />
BidIt tmp_r_begin=r_begin;<br />
tmp_r_begin;<br />
It worked for the POD array but not the container you are using, that is because the assertion is thrown out by the container iterator's  operator.
Thanks for the feedback, I'll look into it.
Regards,
Wong Shao Voon
 modified at 2:53 Monday 7th August, 2006





Hi Petey Boy,
This is a workaround, just define these macros as zeroes to circumvent the assertions, after the inclusion of stdafx.h
<br />
#include "stdafx.h"<br />
<br />
#define _HAS_ITERATOR_DEBUGGING 0<br />
#define _SECURE_SCL 0<br />
#define _SECURE_SCL_THROWS 0<br />
<br />
#include "combination.h"<br />
#include <iostream><br />
#include <vector><br />
#include <deque><br />
#include <list><br />
Please be noted that this workaround will disable the iterator checking.
I have tested vector, deque and list with next_combination in VC8.
Edited the < and > which did not shown up in the code posting
 modified at 4:25 Monday 7th August, 2006





Thanks for the prompt resolution Wong Shao Voon.
I have found Microsoft's STL implementation in VS2005 (8) to be much improved, but often fussy!
Part of what we all love about C and C++ is being able to do 'strange' things to get the job done that are just impossible in other languages.





hi CBasicNet,
thanks a lot for this excellent article! it seems, that it is the only(!) one in the net, which covers Permutations from a set of n elements, from which a sequence of r elements are picked.
one question: I´m using this code in a MSc. thesis and want to cite some reference for it, in order to explain, where the code is coming from. In a forumposting, I found a reference to Donald Knuths "The Art of Computer Programming", but I dont have it at hand, so can you give me some references/hints?
Thanks a lot!!
cheers, flo





Hi Applaus,
I am glad that you find the article excellent. This is only the prev_combination implementation found on the web at that time of writing.
Unfortunately, I wrote this article not based on any references and I have never read Donald Knuths "The Art of Computer Programming".
rgds,
CBasicNet





could i ask you guys how i could include the following conditions in the algorithm (http://www.codeproject.com/cpp/CombC.asp[^]):
in the prev_combination algorithm, is it possible to store each element in the combination to some variable (say P), convert that value to (P)/(P1), and multiply them altogether? example: suppose the elements in my combination are {2, 3}. what i want to happen there is take the value (2)/(21)=2 and (3)/(31)=1.5 and multiply them (thus, the output i want to see is 2*1.5 = 3). or if my combination has the elements {3, 5}, then the algorithm should give me "(3)/(31)=1.5 times (5)/(51)=1.25 = 1.875"..
by the way, i'm no programming expert. i just need this code because i have to evaluate around 16 million combinations of certain numbers and look for the product similar to those examples i gave in the previous paragraph. i'd appreciate the quick response. thanks in advance!
 chris





Thanks for the nice program.
Helped me a lot for some of my activities.
While using the code in another activity found that the program does not work for the repetations
eg: If I give the base as ABACD the program goes in an infinite loop.
~Ankur
 modified at 1:23 Saturday 5th November, 2005





Hi ankur79agr,
The article stated the objects in the n sequence must be distinct, for the source code to work.
Anyway, I already have another version which works for repetition but I haven't gotten time to update this article. The new updated article would have 4 new algorithms.
I'll try my best to update this article as soon as possible but there is no guarantee because I am very busy.
CBasicNet





Thanks CBasicNet for a quick reply.
I will be waiting for the article to get updated... If possible could you please send me a copy of any one method.
Regards,
Ankur





Hi ankur79agr,
I cannot send you a copy of the code because you will need the updated article to teach you how to use the code. Anyway, the updated article will emphasize on the explanation of algorithms more than on how to use my code.
I'll drop you a email when the article is ready, ok?
Best regards,
CBasicNet





your algorithm is flawed it does not calculate all possiblities
You forgot when you move up to B you start with BA
you started with BC
here is a the actually possiblities (assuming you can only use a character once
length of 2, 6 characters (A, B, C, D, E, F)
[code]
Combination Count
====================
AB 1
AC 2
AD 3
AE 4
AF 5
BA 6
BC 7
BD 8
BE 9
BF 10
CA 11
CB 12
CD 13
CE 14
CF 15
DA 16
DB 17
DC 18
DE 19
DF 20
EA 21
EB 22
EC 23
ED 24
EF 25
FA 26
FB 27
FC 28
FD 29
FE 30
[/code]
keep in mind this is assuming that each character can only be used once in the combination
if you allow the characters to be used multiple times in the combination then i have the correct formula for that its (characters) ^ (length)
or the number of characters you can use to power of the length of the combination
for a length of 2 and 6 characters it is really 36
here is the table for that
[code]
Combination Count
====================
AA 1
AB 2
AC 3
AD 4
AE 5
AF 6
BA 7
BB 8
BC 9
BD 10
BE 11
BF 12
CA 13
CB 14
CC 15
CD 16
CE 17
CF 18
DA 19
DB 20
DC 21
DD 22
DE 23
DF 24
EA 25
EB 26
EC 27
ED 28
EE 29
EF 30
FA 31
FB 32
FC 33
FD 34
FE 35
FF 36
[/code]







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

