生成数字组合而不重复的算法
我在这里检查了几乎所有类似的post，但我无法弄清楚我怎么能做我想要的。 我正在尝试的是在C程序中输入一个输入，比如说4号，程序在数组中返回以下数字：
1 2 3 4 12 13 14 23 24 34 123 134 124 1234 更清楚：如果输入数字是4，那么我想使用数字1-4并生成所有可能的数字组合（从1位组合到4位组合），没有数字重复。
我尝试了以下代码：
#include /* Prints out a combination like {1, 2} */ void printc(int comb[], int k) { printf("{"); int i; for (i = 0; i = 0) && (comb[i] >= n - k + 1 + i)) { --i; ++comb[i]; } if (comb[0] > n - k) /* Combination (nk, 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，它们对应一个set，并输出相应的set。
所以我们得到这个代码：
for(int i=1;i<(1<
当n = 4时，输出：
1 2 12 3 13 23 123 4 14 24 124 34 134 234 1234
如果你想按照给定的顺序输出答案，只需将它们作为字符串并将这些字符串放在向量和排序中。
如果n很大，则可以使用bitset。 但是当n> 30时，它可能不会在数小时内终止。 因此int是有效的。
这是一个生成数字组合的程序。 它是用C语言编写的。但它可以用任何其他语言重写。 现在，只需编译并尝试即可！
#include #include 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=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; }
运行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