c++ - 从单个集合中生成所有子集

Question

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

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

score 6 · Accepted Answer

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

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

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

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。

score 2 · Accepted Answer

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

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

您可能会或可能不会采取第一个元素a。
可能会或可能不会采取第二个元素b。
对c.

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

你得到以下八个面具：（按顺序a,b,c）

000 100 010 110 001 101 011 111

生成下一个掩码110：

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

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

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

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

（PS 一个非零整数总是代表真。）

score 0 · Accepted Answer

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

score 0 · Accepted Answer

for (i = 0; (i < n) && mask[i]; ++i)

为了：
从 0 开始，每次将 i 加 1
当 i 小于 n 并且设置了位置 i 的掩码数组中的位时不要停止

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

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

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

c++ - 从单个集合中生成所有子集

4 回答 4

Related

Reference