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

2018-05-31 05:25:27

这是我以前的问题，关于寻找下一个位排列。在我看来，我不得不修改我的代码以实现类似于下一位置换的东西，但却完全不同。

我用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)在i (stated above)的位数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 ，集合中的数字（数字表示位的位置设置为1）

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

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

不确定我是否正确理解你确切想要的，但是基于你的例子（其中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

希望这可以帮助。

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

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

但是，这并不会让我感到非常高效（和/或优雅）。
一个更好的方法是找到一种方法，通过翻转有限的位数来遍历这些数字（我的意思是，你总是需要翻转O（1）位以达到下一个组合，而不是O（n）），这可能允许更有效的迭代（有点像https://en.wikipedia.org/wiki/Gray_code）。
如果我觉得更好，我会编辑或发布另一个更好的。

链接地址: http://www.djcxy.com/p/6369.html

上一篇: Generating bit combination without repetitions (not permunation)

下一篇: Looking for a replayable / somewhat stateless PRNG algorithm