algorithm - 生成子集的最有效方法是什么？

Question

我想做的事情如下:

输入: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;
}

我知道 Gray Code 可以做这样的事情。但我想知道哪一个是生成子集的最有效方法？

Answer 1

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

如果你想提高速度，你可以试试(如果这真的能加速你的代码，请始终分析!):

• 外循环:制作一个使用int的版本而不是 long如果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又到别的地方了。

关于格雷码:这将最大限度地减少位更改的数量，但我看不出这将如何改进所有子集的生成，但是如果您对子集的顺序感兴趣，格雷码很有用特征是它们在遍历它们时仅在一个元素上有所不同。