Generating bit combination without repetitions (not permunation)
Here is my previous question about finding next bit permutation. It occurs to me that I have to modify my code to achieve something similiar to next bit permutation, but quite different.
I am coding information about neighbors of vertex in graph in bit representation of int. For example if n = 4 (n - graph vertices) and graph is full, my array of vertices looks like:
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
First (main) for loop is from 0 to 2^n (cause 2^n is number of subsets of a set).
So if n = 4 , then there are 16 subsets:
{empty}, {1}, ..., {4}, {0,1}, {0,2}, ..., {3,4}, {0,1,2}, ..., {1,2,3}, {1,2,3,4}
These subsets are represented by index value in for loop
for(int i=0; i < 2^n; ++i) // i - represents value of subset
Let's say n = 4 , and actually i = 5 //0101 . I'd like to check subsets of this subset, so I would like to check:
0000
0001
0100
0101
Now I'm generating all bit permutation of 1 bit set, then permutation of 2 bits set ... and so on (until I reach BitCount(5) = 2) and I only take permutation I want (by if statement). It's too many unneeded computations.
So my question is, how to generate all possible COMBINATIONS WITHOUT REPETITIONS (n,k) where n - graph vertices and k - number of bits in i (stated above)
My actual code (that generates all bit permutation and selects wrong):
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);
}
}
}
}
All of this is because I have to count independent set number of every subset of n.
EDIT
I'd like to do it without creating any arrays or generally I'd like to avoid allocating any memory (neither vectors).
A little bit of an explanation: n=5 //00101 - it is bit count of a number i - stated above , k=3 , numbers in set (number represents bit position set to 1)
{
1, // 0000001
2, // 0000010
4, // 0001000
6, // 0100000
7 // 1000000
}
So correct combination is {1,2,6} // 0100011 , but {1,3,6} // 0100101 is a wrong combination. In my code there are plenty of wrong combinations which I have to filter.
Not sure I correctly understand what you exactly want but based from your example (where i==5 ) you want all the subsets of a given subset.
If it's the case you can directly generate all these subsets.
int subset = 5;
int x = subset;
while(x) {
//at this point x is a valid subset
doStuff(x);
x = (x-1)⊂
}
doStuff(0) //0 is always valid
Hope this helps.
My first guess to generate all the possible combinations would be the following rules (sorry if it's a bit hard to read)
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
Applying these rules for n=5 and k=3 would give this:
11100
11010
10110
01110
11001
10101
01101
10011
01011
00111
But that doesn't strikes me as really efficient (and/or elegant).
A better way would be to find a way to iterate through these numbers by flipping only a finite number of bits (i mean, you'd always need to flip O(1) bits to reach the next combination, rather than O(n)), that may allow a more efficient iteration (a bit like the https://en.wikipedia.org/wiki/Gray_code ).
I'll edit or post another andwer if i find better.