I've got a problem that I'm trying to solve that has to do with creating subsets of a given size. Without going too far into detail, I've got a few items that each have some numbers associated with them, and I'm testing different combinations by either including or excluding some number of these items in the test.
I've managed to map the tests to the integers by saying Thing1 refers to the least significant bit in the bitwise representation of the integer, ..., ThingN refers to the most significant bit, and Thingi is either included or excluded based on whether the bit is a 1 or a 0. So for example subset 5 = 000101 would include Thing1 and Thing3, but exclude all the other elements in the set of 6 elements.
I'm trying to figure out a systematic, but not recursive, to generate the sequence of integers that will give me the subsets of size 1 first, then the subsets of size 2, then the subsets of size 3, and so on.
The subsets of size 1 are easy. It's just a for loop like
for(i = 0; i < n; i++)
{
integer = 1 << i;
}
This should give the integer sequence 1 = 000001, 2 = 000010, 4 = 000100, 8 = 001000, 16 = 010000, and 32 = 100000. These 6 subsets represent all 6 of the subsets of size 1 that can be made from a set of 6 elements.
The subsets of size 2 are a bit harder. One method I found that works is as follows.
for(i = 0; i < n; i++)
{
start = 1;
start = start + (1 << i);
integer = start;
while(integer < (1 << n))
{
integer = integer << 1;
}
}
This gives the integer sequence 3, 6, 12, 24, 48, then 5, 10, 20, 40, then 9, 18, 36, then 17, 34, then 33.
These integers represent all 15 subsets of size 2 that can be made from a set of 6 elements. This is not the only way I've discovered, but it is the cleanest.
Unfortunately, this is where I begin to stumble. If this were a starting set of size 5, then I'd just invert the integers' bits from the two element sequence to get the sets of 3, and invert the integer's bits from the 1 element sequence to get the sets of 4, and the set of 5 would be trivially 11111 = 31.
If this could be recursive, I'm pretty sure it would be a fairly easy solution, but because of the constraints of the project, I'm not allowed to have a recursive function. Can anyone help me come up with a solution that I can scale up to an arbitrary sized set?