c - 在C中生成集合的子集(非递归)

Question

我正在尝试以非递归方式生成集合的所有子集。这是代码:

#include <stdio.h>

main() {
    int no_of_element, no_of_subset, i, j, start, index, a[50], x;
    printf("Enter the size of main set :");
    scanf("%d", &no_of_element);
    printf("Enter the elements of main set :");
    for (x = 0; x < no_of_element; x++)
        scanf("%d", &a[x]);
    printf("The subsets are :\n");

    for (no_of_subset = 1; no_of_subset <= no_of_element; no_of_subset++) {
        for (start = 0; start <= no_of_element - no_of_subset; start++) {
            if (no_of_subset == 1)
                printf("%d\n", a[start]);
            else {
                index = start + no_of_subset - 1;
                for (j = index; j < no_of_element; j++) {
                    for (i = start; i < index; i++) {
                        printf("%d\t", a[i]);
                    }
                    printf("%d\n", a[j]);
                }
            }
        }
    }
}

这是输出:

Enter the size of main set :4
Enter the elements of main set :1
2
3
4
The subsets are :
1
2
3
4
1      2
1      3
1      4
2      3
2      4
3      4
1      2      3
1      2      4
2      3      4
1      2      3      4

此代码不会生成子集 (1,3,4)。有人可以帮我解决这个问题吗？

Answer 1

只是为了好玩，我从头开始编写它。诀窍是让计数器遍历所有可能的子集，每个子​​集都是其位的组合。

以防万一，请使用 unsigned long int 处理最多 64 个元素的集合:

#include <stdio.h>

void print_subset(int subset, int *set) {
    int pos=0;
    printf("Subset %d = ", subset);
    while (subset) {
        if (subset & 1) {
            printf("%d ", set[pos]);
        }
        subset >>= 1;
        pos++;
    }
    printf("\n");
}

int main()
{
 int no_of_element,no_of_subset,x,a[50];

 printf("Enter the size of main set :");
     scanf("%d",&no_of_element);
 printf("Enter the elements of main set :");
 for(x=0;x<no_of_element;x++)
     scanf("%d",&a[x]);

 no_of_subset= (1 << no_of_element);
 printf("There are %d subsets\n", no_of_subset);

 for (; no_of_subset--;) {
     print_subset(no_of_subset, a);
 }
}

运行时会产生

Enter the size of main set :4
Enter the elements of main set :1
2
3
4
There are 16 subsets
Subset 15 = 1 2 3 4 
Subset 14 = 2 3 4 
Subset 13 = 1 3 4 
Subset 12 = 3 4 
Subset 11 = 1 2 4 
Subset 10 = 2 4 
Subset 9 = 1 4 
Subset 8 = 4 
Subset 7 = 1 2 3 
Subset 6 = 2 3 
Subset 5 = 1 3 
Subset 4 = 3 
Subset 3 = 1 2 
Subset 2 = 2 
Subset 1 = 1 
Subset 0 =