2

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

#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/

4

4 回答 4

6

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

因为数组是按个位在前排列的,所以它从传统的数字符号向后看。

与其使用布尔值数组,不如使用一个数字和++运算符的二进制表示中的位。

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。

于 2012-06-03T11:29:56.857 回答
2

去年我参加了第 6 届 ITAT 比赛的 C 语言比赛,在那里我通过在掩码的帮助下生成所有组合来解决第二个问题(尽管它可能不是该问题的最佳解决方案。)

当您尝试导出 的所有子集时{a,b,c},您可以这样做:

  1. 您可能会或可能不会采取第一个元素a
  2. 可能会或可能不会采取第二个元素b
  3. c.

因此,您最终得到了一组 3 个接受或不接受的选择。这可以用二进制或布尔值表示:表示采用1,而不采用0

你得到以下八个面具:(按顺序a,b,c

000 100 010 110 001 101 011 111

生成下一个掩码110

  1. 元素 0 是1. 切换到0.
  2. 元素 1 是1. 切换到0.
  3. 元素 2 是0。切换到1.
  4. 现在你有001which 是下一个掩码,它生成 subset {c}

for (i = 0; (i < n) && mask[i]; ++i)正是这样做的。

  1. 从元素 0 开始。
  2. 而(i不超过你的掩码长度和元素 i 是1
  3. 执行将 i 翻转为0和 ++i 的正文代码(转到下一个元素)。转到 2(检查)。

如果当前掩码是111(最后一个掩码),则next()函数简单地返回1以指示 END。

(PS 一个非零整数总是代表真。)

于 2012-06-03T11:51:42.923 回答
0

问题中的循环从数组的开头开始,并将所有 1 设置为 0,直到遇到 0。下一条语句将此 0 设置为 1(如果可能)。所以会发生什么: 0,0,0 -> 1,0,0 -> 0,1,0 -> 1,1,0 -> 0,0,1... 我不是铁杆 C 程序员,但我认为这可以通过使用一个位字段并迭代地递增 1 来完成。

于 2012-06-03T11:30:34.847 回答
0
for (i = 0; (i < n) && mask[i]; ++i)
  1. 为了:
  2. 从 0 开始,每次将 i 加 1
  3. 当 i 小于 n 并且设置了位置 i 的掩码数组中的位时不要停止

这真的很简单:for 语句的 3 个部分:初始状态;结束条件;手术。

因此,如果您可以理解for (i=0; i < 5; i++)意味着从 0 开始并每次将 i 递增 1 直到它小于 5,您就可以理解您询问的更复杂的 for 循环。

在这种情况下,它通过循环寻找未设置的掩码的第一个元素,清除每个元素,然后执行一些其他操作 - 即如果没有设置掩码位,并且它到达末尾的数组。在我看来,这是一种仅将数组的一个元素设置为 1 的简单方法,依次得到结果:100、010、001

于 2012-06-03T11:33:03.877 回答