从单个集合生成所有子集

Question

我试图理解代码从一组生成所有子集.这是代码

#include <stdio.h>

/* Applies the mask to a set like {1, 2, ..., n} and prints it */
void printv(int mask[], int n) {
    int i;
    printf("{ ");
    for (i = 0; i < n; ++i)
        if (mask[i])
            printf("%d ", i + 1); /*i+1 is part of the subset*/
    printf("\\b }\\n");
}

/* Generates the next mask*/
int next(int mask[], int n) {
    int i;
    for (i = 0; (i < n) && mask[i]; ++i)
        mask[i] = 0;

    if (i < n) {
        mask[i] = 1;
        return 1;
    }
    return 0;
}

int main(int argc, char *argv[]) {
    int n = 3;

    int mask[16]; /* Guess what this is */
    int i;
    for (i = 0; i < n; ++i)
        mask[i] = 0;

    /* Print the first set */
    printv(mask, n);

    /* Print all the others */
    while (next(mask, n))
        printv(mask, n);

    return 0;
}

我不明白for (i = 0; (i < n) && mask[i]; ++i)下一个函数中这一行背后的逻辑.如何在这里生成下一个掩码？

代码和算法在这里查看:http: //compprog.wordpress.com/2007/10/10/generating-subsets/

Answer 1

这只是一个二进制计数的实现.基本思想是将最不重要(最后)零更改为一,并将其​​后的所有零更改为零.如果被解释为二进制数,则"下一个"掩码将比前一个掩码"多一个".

因为数组首先排列在一个位置,所以它从传统的数字符号向后看.

它也可以使用一个数字和++运算符的二进制表示中的位,而不是使用布尔值数组.

int next(int &mask, int n) { // using C++ reference
    if ( mask == ( 1u << n ) - 1 ) return 0;
    ++ mask;
    return 1;
}

void printv(int mask, int n) {
    int i;
    printf("{ ");
    for (i = 0; i < n; ++i)
        if (mask & ( 1 << i ) )
            printf("%d ", i + 1); /*i+1 is part of the subset*/
    printf("\\b }\\n");
}

我已经使用了一点C++,因为你标记了这个问题,但是发布的代码是简单的C.