I checked almost every similar post in here but I couldn't figure out how I can do what I want. What I am trying is to give an input in a C program, let say number 4, and the program return the following numbers in an array:
1
2
3
4
12
13
14
23
24
34
123
134
124
1234
To be more clear: If the input number is 4 then i want to use digits 1-4 and generate all the possible combinations of digits(from 1-digit combinations to 4-digit combinations) without digit repetitions.
I tried the following code:
#include <stdio.h>
/* Prints out a combination like {1, 2} */
void printc(int comb[], int k) {
printf("{");
int i;
for (i = 0; i < k; ++i)
printf("%d, ", comb[i] + 1);
printf("\\b\\b}\\n");
}
int next_comb(int comb[], int k, int n) {
int i = k - 1;
++comb[i];
while ((i >= 0) && (comb[i] >= n - k + 1 + i)) {
--i;
++comb[i];
}
if (comb[0] > n - k) /* Combination (n-k, n-k+1, ..., n) reached */
return 0; /* No more combinations can be generated */
/* comb now looks like (..., x, n, n, n, ..., n).
Turn it into (..., x, x + 1, x + 2, ...) */
for (i = i + 1; i < k; ++i)
comb[i] = comb[i - 1] + 1;
return 1;
}
int main(int argc, char *argv[]) {
int n = 5; /* The size of the set; for {1, 2, 3, 4} it's 4 */
int k = 3; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
int comb[16]; /* comb[i] is the index of the i-th element in the
combination */
/* Setup comb for the initial combination */
int i;
for (i = 0; i < k; ++i)
comb[i] = i;
/* Print the first combination */
printc(comb, k);
/* Generate and print all the other combinations */
while (next_comb(comb, k, n))
printc(comb, k);
return 0;
}
The above program prints the result. I want to get the result somehow.. but I can't because the above code prints the result in a strange manner.
We use a int to represent a set. For the i-th bit, if it is 1, then i is in the set and vice versa.
Take a example:1010(2)={4,2} 1111(2)={4,3,2,1}
For every element that will be considered, there is two choices: in or not in the set.
So, there are 2^n different set in total. And in my code, I just enumerate every possible int which is corresponding a set, and output the corresponding set.
So we get this code:
for(int i=1;i<(1<<n);i++)
{
for(int j=0;j<n;j++)
if ((1<<j)&i) printf("%d",j+1);
puts("");
}
when n=4, output:
1
2
12
3
13
23
123
4
14
24
124
34
134
234
1234
If you want to output the answer as the order of giving, just make them string and put these string in vector and sort.
If n is large, you can use bitset. But when n>30,it may not be terminates in hours. So int is efficient.