我在这里检查了几乎所有类似的帖子,但是我不知道该怎么做。我正在尝试在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,则表示我在集合中,反之亦然。
例如: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
如果要按照给出的顺序输出答案,只需将它们制成字符串,然后将这些字符串放入向量中并进行排序。
如果n大,则可以使用位集。但是,当n> 30时,它可能不会在数小时内终止。所以int是有效的。