我试图理解从一组生成所有子集的代码。这是代码
#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/geneating-subsets/ http://compprog.wordpress.com/2007/10/10/generating-subsets/
这只是一个实现以二进制计数 http://en.wikipedia.org/wiki/Binary_numeral_system#Counting_in_binary。基本思想是将最不重要的(最后一个)零更改为 1,并将其后面的所有 0 更改为 0。如果将“下一个”掩码解释为二进制数,则“下一个”掩码将比前一个掩码“多一个”。
因为数组是按照个位在前排列的,所以它与传统的数字表示法是向后看的。
它不使用布尔值数组,而是使用一个数字的二进制表示形式中的位和++
操作员。
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 代码。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)