生成没有重复的位组合（不是排列）

Question

这是我之前 question 关于寻找下一位排列的内容。我突然想到我必须修改我的代码来实现类似于下一位排列的东西，但完全不同。

我正在用 int 的位表示来编码关于图中顶点邻居的信息。例如，如果 n = 4（n - 图顶点）并且图已满，我的顶点数组如下所示：

vertices[0]=14 // 1110 - it means vertex no. 1 is connected with vertices no. 2, 3, and 4
vertices[1]=13 // 1101 - it means vertex no. 2 is connected with vertices no. 1, 3, and 4
vertices[2]=11 // 1011 - it means vertex no. 3 is connected with vertices no. 1, 2, and 4
vertices[3]=7  // 0111 - it means vertex no. 4 is connected with vertices no. 1, 2, and 3

第一个（主要）for 循环是从 0 到 2^n（因为 2^n 是集合的子集数）。

所以如果n = 4，那么有16个子集：

{empty}, {1}, ..., {4}, {0,1}, {0,2}, ..., {3,4}, {0,1,2}, ..., {1,2,3}, {1,2,3,4}

这些子集在for循环中用索引值表示

for(int i=0; i < 2^n; ++i) // i - represents value of subset

比方说 n = 4，实际上 i = 5 //0101。我想检查这个子集的子集，所以我想检查：

现在我正在生成 1 位集合的所有位排列，然后是 2 位集合的排列...等等（直到我达到 BitCount(5) = 2）并且我只进行我想要的排列（通过if语句）。太多不必要的计算了。

所以我的问题是，如何生成所有可能的无重复组合 (n,k)，其中 n - 图顶点和 k - i (stated above)

中的位数

我的实际代码（生成所有位排列并选择错误）：

for (int i = 0; i < PowerNumber; i++) 
    {
        int independentSetsSum = 0;
        int bc = BitCount(i);

        if(bc == 1) independentSetsSum = 1;
        else if (bc > 1)
        {           
            for(int j = 1; j <= bc; ++j)
            {
                unsigned int v = (1 << j) - 1; // current permutation of bits 
                int bc2 = BitCount(j);
                while(v <= i)
                {
                    if((i & v) == v)
                        for(int neigh = 1; neigh <= bc2; neigh++)
                            if((v & vertices[GetBitPositionByNr(v, neigh) - 1]) == 0)
                                independentSetsSum ++;

                    unsigned int t = (v | (v - 1)) + 1;  
                    v = t | ((((t & -t) / (v & -v)) >> 1) - 1);     
                } 
            }
        }
    }

所有这些都是因为我必须计算n的每个子集的独立集数。

编辑

我想在不创建任何数组的情况下执行此操作，或者通常我想避免分配任何内存（既不是向量）。

一点解释： n=5 //00101 - it is bit count of a number i - stated above, k=3, numbers in set (numbers表示bit position set to 1)

{
1, // 0000001
2, // 0000010
4, // 0001000
6, // 0100000
7  // 1000000
}

所以正确的组合是{1,2,6} // 0100011，但是{1,3,6} // 0100101是错误的组合。在我的代码中有很多错误的组合我必须过滤。

Answer 1

我的第一个猜测是生成所有可能的组合是以下规则（抱歉，如果它有点难以阅读）

start from the combination where all the 1s are on the left, all the 0s are on the right

move the leftmost 1 with a 0 on its immediate right to the right
if that bit had a 1 on its immediate left then
  move all the 1s on its left all the way to the left

you're finished when you reach the combination with all the 1s on the right, and all the 0s on the left

对 n=5 和 k=3 应用这些规则会得到：

11100
11010
10110
01110
11001
10101
01101
10011
01011
00111

但这并没有让我印象深刻（and/or 优雅）。
更好的方法是找到一种方法，通过仅翻转有限数量的位来迭代这些数字（我的意思是，您总是需要翻转 O(1) 位才能达到下一个组合，而不是 O(n) )，这可能允许更有效的迭代（有点像 https://en.wikipedia.org/wiki/Gray_code ）。
如果我发现更好，我会编辑或post另一个andwer。

Answer 2

不确定我是否正确理解了您的确切需求，但根据您的示例（i==5），您需要给定子集的所有子集。

如果是这种情况，您可以直接生成所有这些子集。

int subset = 5;
int x = subset;
while(x) {
    //at this point x is a valid subset
    doStuff(x);
    x = (x-1)&subset;
}
doStuff(0) //0 is always valid

希望对您有所帮助。

生成没有重复的位组合（不是排列）

Generating bit combination without repetitions (not permunation)

c++

algorithm

graph

bit-manipulation

combinations

编辑