从单个集合生成所有子集 [英] Generating all subsets from a single set

问题描述

我试图理解代码以从一个集合生成所有子集。这是代码

I was trying to understand the code to generate all the subsets from one set. Here is the code

#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

I am not understand the logic behind this line for (i = 0; (i < n) && mask[i]; ++i) inside the next function. How is the next mask being generated here?

这里的代码和算法如下：
http://compprog.wordpress.com/2007/10/10/generating-subsets/

Code and algorithm looked here: http://compprog.wordpress.com/2007/10/10/generating-subsets/

推荐答案

这只是一个二进制计数的实现。基本思想是将最低有效（最后一个）零更改为一，并将后面的所有后的零更改为零。

That is simply an implementation of counting in binary. The basic idea is to change the least-significant (last) zero to a one, and change all the ones after it to zeroes. The "next" mask will be "one more" than the previous if interpreted as a binary number.

由于数组首先排列在一个位置，因此它向后看从传统的数字符号。

Because the array is arranged with the one's place first, it looks backwards from traditional numeric notation.

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

Instead of using an array of Boolean values, it could just as well use the bits in the binary representation of one number and the ++ operator.

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。

I've used a little C++ since you tagged the question as such, but the posted code is plain C.

这篇关于从单个集合生成所有子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！