子集枚举

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
//枚举包含n个元素的集合中大小是k的子集
void subset_n_k(int n,int k){
    int sub = 1;
    int end_state;
    for(int i= 1;i<k;i++){
        sub<<=1;
        sub|=1;
    }
    end_state = sub<<(n-k);
    while(1){
        for(int i=0;i<n;i++){
            printf("%d ",(sub&(1<<i))?1:0);
        }
        printf("
");
        if(sub == end_state) break;
        int x = sub&(-sub);
        int y = sub+x;
        sub = ((sub&(~y))/x >> 1 )|y;
    }
}

//枚举包含n个元素的全部子集
void subset_n(int n){
    for(int sub = 0;sub<(1<<n);sub++){
        for(int i=0;i<n;i++){
            printf("%d ",(sub&(1<<i))?1:0);
        }
        printf("
");
    }
}

//枚举集合state的所有子集
void subset_state(int state){
    int sub = state;
    int n = 1 + (int)(log(state+0.5)/log(2.0));
    printf("n : %d
",n);
    while(1){
        for(int i=0;i<n;i++){
            printf("%d ",(sub&(1<<i))?1:0);
        }
        printf("state %d
",state);
        if(sub==0)break;
        sub = (sub - 1)&state;
    }
}

int main(){
    int n,k;
    int state = 5;
    scanf("%d%d",&n,&k);
    scanf("%d",&state);
    printf("from subset_n_k
");
    subset_n_k(n,k);
    printf("from subset_n
");
    subset_n(n);
    printf("from subset_state
");
    subset_state(state);
    return 0;
}