生成数字组合而不重复的算法

  • Z时代
  • 2024-01-10
  • 分类：问答

我在这里检查了几乎所有类似的帖子，但是我不知道该怎么做。我正在尝试在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是有效的。

以上是 生成数字组合而不重复的算法 的全部内容， 来源链接： utcz.com/qa/418077.html

回到顶部