本文介绍了从单个集合生成所有子集的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我试图理解代码以从一个集合生成所有子集。这是代码
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?
这里的代码和算法如下:
Code and algorithm looked here:http://compprog.wordpress.com/2007/10/10/generating-subsets/
推荐答案
这只是一个二进制计数的实现。基本思想是将最低有效(最后一个)零更改为一,并将后面的所有后的零更改为零。
而不是使用布尔值数组,它可以使用一个数字的二进制表示的位和
++
运算符。
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.
这篇关于从单个集合生成所有子集的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!