I don't have a closed form for the function, but I have bit hacking not related to the next_combination , which you can use if that helps. It is assumed that you can put the bitmask in some integer type, which is probably not an unreasonable assumption, given that there are 2 64 for a 64-element set.
As the commentary says, I find this definition of “lexicographic ordering” a bit strange, since I would say that lexicographic ordering would be: [], [a], [ab], [abc], [ac], [b], [bc], [c] . But I had to do first "first by size, and then by lexicographic" listing.
// Generate bitmaps representing all subsets of a set of k elements, // in order first by (ascending) subset size, and then lexicographically. // The elements correspond to the bits in increasing magnitude (so the // first element in lexicographic order corresponds to the 2^0 bit.) // // This function generates and returns the next bit-pattern, in circular order // (so that if the iteration is finished, it returns 0). // template<typename UnsignedInteger> UnsignedInteger next_combination(UnsignedInteger comb, UnsignedInteger mask) { UnsignedInteger last_one = comb & -comb; UnsignedInteger last_zero = (comb + last_one) &~ comb & mask; if (last_zero) return comb + last_one + (last_zero / (last_one * 2)) - 1; else if (last_one > 1) return mask / (last_one / 2); else return ~comb & 1; }
Line 5 performs the bit-hacker equivalent of the (extended) regular expression replacement, which finds the last line 01 in the line, flips it to 10 and shifts all of the next 1 all right.
s/01(1*)(0*)$/10\2\1/
Line 6 does this (only if the previous one failed) add another 1 and push 1 all the way to the right:
s/(1*)0(0*)/\21\1/
I don't know if this explanation helps :)
Here's a quick and dirty driver (the command line argument is the set size, defaults to 5, the maximum number of bits in an unsigned long):
#include <iostream> template<typename UnsignedInteger> std::ostream& show(std::ostream& out, UnsignedInteger comb) { out << '['; char a = 'a'; for (UnsignedInteger i = 1; comb; i *= 2, ++a) { if (i & comb) { out << a; comb -= i; } } return out << ']'; } int main(int argc, char** argv) { unsigned int n = 5; if (argc > 1) n = atoi(argv[1]); unsigned long mask = (1UL << n) - 1; unsigned long comb = 0; do { show(std::cout, comb) << std::endl; comb = next_combination(comb, mask); } while (comb); return 0; }
It is hard to believe that this function can be useful for a collection of more than 64 elements, given the size of the enumeration, but it may be useful to list some limited part, such as all subsets of three elements. In this case, bit hackers are really useful if the modification fits into one word. Fortunately, this is easy to verify; you just need to perform the calculation, as indicated above, on the last word in the bitet, before the test for last_zero , which is zero. (In this case, you do not need to beat mask , and indeed, you can choose a different way of specifying the specified size.) If last_zero turns out to be zero (which will be really quite rare), then you need to do the conversion in some other way, but the principle the same: find the first 0 that precedes 1 (pay attention to the case when 0 is at the end of a word and 1 at the beginning of the next); change the value of 01 to 10 , find out how much 1 you need to move and move them to the end.