我查看了这里几乎所有类似的帖子，但我不知道如何才能做到我想要的。我正在尝试的是在C程序中给出一个输入，比如数字4，程序在数组中返回以下数字:
1
2
3
4
12
13
14
23
24
34
123
134
124
1234
更清楚:如果输入的数字是4，那么我想使用数字1-4，并生成所有可能的数字组合(从1位组合到4位组合)，没有数字重复。
我尝试了以下代码:
#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;
}
上面的程序输出结果。不管怎样，我想要得到结果。但是我不能，因为上面的代码以一种奇怪的方式打印结果。
使用int型来表示集合。对于第i位，如果它是1，则i在集合中，反之亦然。
取一个例子:1010(2)={4,2}1111(2)={4、3、2、1}
对于要考虑的每个元素，有两个选择:在或不在集合中。
所以总共有2^n个不同的集合。在我的代码中，我只是列举了每一个可能的int，它对应于一个集合，并输出相应的集合。
所以我们得到这个代码:for(int i=1;i<(1<<n);i++)
{
for(int j=0;j<n;j++)
if ((1<<j)&i) printf("%d",j+1);
puts("");
}
当n=4时，输出:
1
2
12
3
13
23
123
4
14
24
124
34
134
234
1234
如果你想按照给出的顺序输出答案，只要把它们变成字符串，然后把这些字符串放在vector中并排序。
如果n很大，可以使用bitset。但当n>30时，它可能不是以小时为单位终止的。所以int是有效的。
这是一个生成数字组合的程序。它是用C语言写的。但它可以用任何其他语言重写。现在，只需编译它并尝试一下!
#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
接受的答案中的注释问道:
"伟大的简短的解决方案，有没有办法改变它，使它产生的组合顺序?如1、2、3、4、12、13、23、14、24、34,123,124,134,234、1234"
下面的程序将按此顺序生成这些组合。
这个程序的工作方式与被接受的答案相同——使用数字的底层二进制模式来找到组合。
程序首先显示C(4,0)，然后是C(4,1)，接着是C(4,2)， C(4,3)，最后是C(4,4)。
程序可以很容易地扩展。只需要增加n的值，并在数组中加上2的相应次幂。虽然效率不高，但程序确实产生了所要求的组合序列。
/* Combin.c -- display the combinations of n objects
to omit the empty set, C(n,0), change the start value in the for loop in
the main function from 0 to 1
*/
#include <stdio.h>
int numOfSetBits(int num)
{
int count = 0;
while (num > 0) {
if ((num & 1) == 1) {
++count;
}
num /= 2;
}
return count;
}
void displayComb(int n, int r)
{
int power2[] = { 1, 2, 4, 8, 16 };
for (int i = 0; i < power2[n]; ++i) {
if (numOfSetBits(i) == r) {
printf(" {");
for (int j = 0; j < n; ++j) {
if (i & power2[j]) {
putchar((j + 1) + '0');
}
}
putchar('}');
}
}
}
int main (void)
{
putchar('n');
int n = 4;
for (int i = 0; i <= n; ++i) {
printf("C(%d,%d) =", n, i);
displayComb(n, i);
putchar('n');
}
return 0;
}
程序输出:
C(4,0) = {}
C(4,1) = {1} {2} {3} {4}
C(4,2) = {12} {13} {23} {14} {24} {34}
C(4,3) = {123} {124} {134} {234}
C(4,4) = {1234}