Combinations number in c language

Ken H

12y2k

hello friend,
How to use a combination number of non-recursive functions?
// Codes:
#include
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.:)

8 Replies

Know the answer? Post it — somebody with the same question will find it here.

Vulpes12y ago
Accepted 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 << (n - 1); /* 2 to power n */
z = 0;

/* consider all binary numbers less than max with exactly
m non-zero bits
*/
x = 1;
while (x < max)
{
/* initialize indices to impossible value */
for(i = 0; i < max ; i++) indices[i] = -1;
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 < max; i++)
{
if (indices[i] > -1) printf("%d", a[indices[i]]);
}
printf ("\n");
z++; /* increment number of combinations */
}

x++;
}
printf("Total:%d\n", 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 << (n - 1); /* 2 to power n */
z = 0;
/* consider all binary numbers less than max with exactly
m non-zero bits
*/
x = 1;
while (x < max)
{
/* initialize indices to impossible value */
for(i = 0; i < max ; i++) indices[i] = -1;
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 < max; i++)
{
if (indices[i] > -1) printf("%c", b[indices[i]]);
}
printf ("\n");
z++; /* increment number of combinations */
}

x++;
}

printf("Total:%d\n", 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("\n");
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
Ken H12y ago
Thank you very much for your explanation. :)
Vulpes12y ago
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.
Ken H12y ago
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 << (n - 1); /* The max value will as 32. */

------------------
Decimal Binary
------------------
7 111
11 1011
13 1101
14 1110
19 10011
21 10101

And so on
... ...
Vulpes12y ago
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 H12y ago
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. :)
Vulpes12y ago
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 H12y ago
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("\n");
}

inline void print_NewC(const char a[],const int t[],int m) // print result.
{
for(int i=0;i
printf("\n");
}
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\n",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\n",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("\n");
C(b,5,3);
}