algorithm for generating number combinations without repetition
Solution 1
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.
Solution 2
Here is a program that generates combinations of numbers. It is written in C. But it could be rewritten in any other language. For now, just compile it and try it !
#include <stdio.h>
#include <stdlib.h>
int v[100], stack[100];
int sp,i,n,g;
int main()
{
printf("Dimension of V:");
scanf( "%d",&n);
//Input numbers
for (i=0 ; i<n ; i++) {
printf("V[%d]=",i);
scanf( "%d",&g);
v[i]=g;
}
printf("running...\n");
sp=-1;
while(1) {
// stack ones until stack overflow
while(sp<n-1) {
sp=sp+1;
stack[sp]=1;
for (i=0 ; i<=sp ; i++) if (stack[i]==1) printf("v[%d]=%d ",i,v[i]);
printf("\n");
}
// unstack all the zeros until top of stack is equal one
while (stack[sp]==0 && sp>=0) sp=sp-1;
// if Bottom of stack is reached then stop
if (sp<0) break;
// set top of stack from one to zero
stack[sp]=0;
}
return 0;
}
run for n=4 :
[oldache@localhost fin]$ ./comb
Dimension of V:4
V[0]=10
V[1]=20
V[2]=30
V[3]=40
running...
v[0]=10
v[0]=10 v[1]=20
v[0]=10 v[1]=20 v[2]=30
v[0]=10 v[1]=20 v[2]=30 v[3]=40
v[0]=10 v[1]=20 v[3]=40
v[0]=10 v[2]=30
v[0]=10 v[2]=30 v[3]=40
v[0]=10 v[3]=40
v[1]=20
v[1]=20 v[2]=30
v[1]=20 v[2]=30 v[3]=40
v[1]=20 v[3]=40
v[2]=30
v[2]=30 v[3]=40
v[3]=40
Comments
-
Dchris almost 2 years
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.
-
WhozCraig about 11 yearsFor solving the specific problem the OP is having, this is wonderful. I honestly not sure it is standard-portable (I think it is, but would need to read up a bit). if so, it will work for numbers up to
(sizeof(int)*8)-2
, and you could squeeze that extra bit out if you usedunsigned int
. If larger sizes were needed a byte-array with an extra loop would easily be incorporated. All in all, a nice answer. -
rliu about 11 yearsI think adding a description at the top for why the algorithm works would be nice. This algorithm generates the (unordered) sets and represents them with a set of bits. So
{1, 2, 3, 4} = 1111
and{} = 0000
and{1, 3} = 1010
, etc. It goes through all of the bit sets and generates the corresponding set of numbers by checking if that bit is "on" (i.e.== 1
) and prints it if that's the case. Ah I just noticed it doesn't print the empty set, but that may or may not be desirable. -
rliu about 11 yearsAh, I screwed up the ordering. It's more like
{4, 3, 2, 1} = 1111
(instead of{1, 2, 3, 4} = 1111
) -
DeepS1X almost 6 yearsI find your lack of indentation... Disturbing.
-
GioGio over 2 yearsGreat short solution, is there a way to change it such that it generates the combinations in order? Such as 1,2,3,4,12,13,23,14,24,34,123,124,134,234,1234