我试图理解代码以从一个集合生成所有子集。这是代码
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? 这里的代码和算法如下: compprog.wordpress/2007/10/10/generating-subsets/ Code and algorithm looked here:
compprog.wordpress/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. 我使用了一个C ++,因为你标记了这样的问题,发布的代码是简单的C。 I've used a little C++ since you tagged the question as such, but the posted code is plain C.
更多推荐
从单个集合生成所有子集
发布评论