1

我想要做的如下：

输入：n，例如 n = 3

输出：{000, 001, 010, 011, 100, 101, 110, 111}，生成所有子集，我不在乎子集的顺序

我已经实现了一个算法：

for (long i = 0, max = 1 << n; i < max; i++) {
    for (int j = 0; j < n; j++) {
        // check if the j bit is set to 1
        int isSet = (int) i &  1 << j;
        if (isSet > 0) {
            // if yes, set the corresponding jth bit of x as 1.
        }
    }
    // add x to results;
}

我知道格雷码可以做这样的事情。但我想知道哪一种是生成子集的最有效方法？

4

1 回答 1

2

我不确定您的确切意思是“最有效”，但是如果您寻求速度优化，您只能希望进行一些小的优化，因为我怀疑您是否能找到更快的算法。

如果您想提高速度，请尝试一下（如果这确实加快了您的代码速度，请始终配置文件！）：

  • 外循环：制作一个使用int而不是longif的版本max足够小以适合int. 这可能会更快。
  • 内循环：您可以计算两个循环外的所有位测试掩码并将它们存储在一个数组中。这样您就可以用1 << j数组查找替换。[我不确定这是否会提高速度，但值得一试]

你也应该更换

int isSet = (int) i &  1 << j;
if (isSet > 0) {
    // if yes, set the corresponding jth bit of x as 1.
}

经过：

if (0!=(int) i &  1 << j) {
    // if yes, set the corresponding jth bit of x as 1.
}

除非您isSet再次在其他地方需要该变量。

关于格雷码：这将最大限度地减少比特变化的数量，但我看不出这可以如何改进所有子集的生成，但是格雷码很有用，如果您对具有以下特征的子集的顺序感兴趣在迭代它们时仅在一个元素上有所不同。

于 2015-12-21T10:16:18.653 回答