Combinations number in c language

Question

hello friend,
How to use a combination number of non-recursive functions?
// Codes:
#include<stdio.h>
void C(int a[],int n,int m){
// How to do it?

}
void C(char b[],int n,int m){
// How to do it?
}
void main()
{

int a[5]={1,2,3,4,5};

char b[]={"abcde"};

C(a,5,3); // It should be 10 combinations.

C(b,5,3); // Same as above.

}

Here is its formula:

Such as:
C(a,5,3);
It will print the following information:
123
124
125
134
135
145
234
235
245
345
Total:10
C(b,5,3);
It will print the following information:
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
Total:10
Please use a non-recursive method to solve it(Do not use the system to provide any built-in functions). And explain its problem-solving ideas.
Thank for you.:)

Vulpes · Answer

If the order in which the combinations are printed is unimportant, then the following should work fine. The algorithm I've used is to consider all binary numbers less than 2^n which contain exactly 'm' non-zero bits. The positions of these bits are then used to generate a combination of the corresponding elements of the array: #include void C(int a[],int n,int m) { int x; /* stores binary number */ int c; /* counts non-zero bits */ int i; /* for statement variable */ int k; /* bit position */ int t; /* temporary variable */ int z; /* counts number of combinations printed */ int indices[ 1024 ]; /* stores indices of non-zero bits - EDITED */ int max = 2 z = 0; /* consider all binary numbers less than max with exactly m non-zero bits */ x = 1; while (x { /* initialize indices to impossible value */ for(i = 0; i t = x; k = 0; c = 0; /* generate bits of binary number, x */ while (t > 0) { if ((t % 2) == 1) { indices[c] = k; /* if non-zero store the bit position */ c++; /* count it */ } k++; /* increment bit position */ t /= 2; /* divide t by 2 */ } /* if there are exactly m non-zero bits print the corresponding elements of the array */ if (c == m) { for(i = 0; i { if (indices[i] > -1) printf("%d", a[indices[i]]); } printf ("
"); z++; /* increment number of combinations */ } x++; } printf("Total:%d
", z); /* print number of combinations */ } void C2(char b[],int n,int m) { int x; /* stores binary number */ int c; /* counts non-zero bits */ int i; /* for statement variable */ int k; /* bit position */ int t; /* temporary variable */ int z; /* counts number of combinations printed */ int indices[ 1024 ]; /* stores indices of non-zero bits - EDITED */ int max = 2 z = 0; /* consider all binary numbers less than max with exactly m non-zero bits */ x = 1; while (x { /* initialize indices to impossible value */ for(i = 0; i t = x; k = 0; c = 0; /* generate bits of binary number, x */ while (t > 0) { if ((t % 2) == 1) { indices[c] = k; /* if non-zero store the bit position */ c++; /* count it */ } k++; /* increment bit position */ t /= 2; /* divide t by 2 */ } /* if there are exactly m non-zero bits print the corresponding elements of the array */ if (c == m) { for(i = 0; i { if (indices[i] > -1) printf("%c", b[indices[i]]); } printf ("
"); z++; /* increment number of combinations */ } x++; } printf("Total:%d
", z); /* print number of combinations */ } void main() { int a[5]={1,2,3,4,5}; char b[]={"abcde"}; C(a,5,3); /* It should be 10 combinations. */ printf("
"); C2(b,5,3); /* Same as above. */ } The output is: 123 124 134 234 125 135 235 145 245 345 Total:10 abc abd acd bcd abe ace bce ade bde cde Total:10

Vulpes · Answer

If you have an array of 5 values, then the 5 digit binary numbers from 00001 to 11111 (1 to 31 decimal) can be used to represent all possible combinations of those values. The presence of a 1 or 0 at a certain position in the binary number determines whether the value at that index in the array appears in a combination or not. So, there's only one combination which contains all 5 values which is represented by the binary number 11111 and there are 5 combinations which contain exactly 4 of the values which are represented by the binary numbers 01111, 10111, 11011, 11101 and 11110. In the latter case, the presence of the 0 determines which value is to be omitted when determining combinations of the 4 other values. Using similar logic, there are 10 numbers which contain exactly 3 of the values and so by iterating through all 5 digit binary numbers and finding those which contain exactly three 1's, we can generate the combinations themselves.

Vulpes · Answer

Sorry, I only made the indices array big enough to cope with 5 numbers and so, if you've been trying to run it with larger sets, you will get an error. I've altered it now so it can deal with up to 10 numbers - probably as many as you'd want to do here - but, as you're own version (which uses a different algorithm), seems to be working fine and producing output in lexographical order, I'd go with that instead :)

Ken H · Answer

Thank you very much for your explanation. :)

Ken H · Answer

When I found the following in the debug decimal number can match the number of combinations. It makes me baffled. I would like to know on what basis, or what the law. Such as: C(a,5,3); int max = 2 ------------------ Decimal Binary ------------------ 7 111 11 1011 13 1101 14 1110 19 10011 21 10101 And so on ... ...

Vulpes · Answer

2 ^ n is the number of n-digit binary numbers. Each digit can be chosen in 2 ways, 0 or 1. So there are 2 x 2 ... x 2 (to n terms) = 2 ^ n such numbers. Seasons greetings to you too :)

Ken H · Answer

Thank for you. However, I still baffled why use '2 ^ n' can get the number of combinations. So, I use another algorithm lexicography order. I wish you a Merry Christmas. Happy New Year. :)

Ken H · Answer

Thank for you, Vulpes. It has a runtime error: Run-Time Check Failure #2 - Stack around the variable 'indices' was corrupted. Also, I modified your code. The modified code: It will look more in line with the requirements (because it is the right order). :) #include inline void print_NewC(const int a[],const int t[],int m) // print result. { for(int i=0;i printf("
"); } inline void print_NewC(const char a[],const int t[],int m) // print result. { for(int i=0;i printf("
"); } bool C(int a[],int n,int m) { if(m>n) return false; // Does not allow such a situation occur. int temp[10]; // Assuming only a maximum of 10 elements. int i,k,Total; i=k=Total=0; for(i=0;i temp[k]=0; while(true){ if(temp[k]>=n) { if(k==0) break; // No need to compare. --k; temp[k]+=1; } else if(k==m-1) // Completed new combination. { print_NewC(a,temp,m); temp[k]+=1; // Continue to move to the next one. Total++; } else { ++k; // Move to the next one. temp[k]=temp[k-1]+1; // } } printf("Total:%d
",Total); // print number of combinations return true; } bool C(char a[],int n,int m) // Same as above. { if(m>n) return false; // Does not allow such a situation occur. int temp[10]; // Assuming only a maximum of 10 elements. int i,k,Total; i=k=Total=0; for(i=0;i temp[k]=0; while(true){ if(temp[k]>=n) { if(k==0) break; // No need to compare. --k; temp[k]+=1; } else if(k==m-1) // Completed new combination. { print_NewC(a,temp,m); temp[k]+=1; // Continue to move to the next one. Total++; } else { ++k; // Move to the next one. temp[k]=temp[k-1]+1; // } } printf("Total:%d
",Total); // print number of combinations. return true; } void main(void) { int a[5]={1,2,3,4,5}; char b[6]={"abcde"}; C(a,5,3); printf("
"); C(b,5,3); }

Combinations number in c language

Answers (8)