Combinatorial Number System - Applications

Applications

One could use the combinatorial number system to list or traverse all k-combinations of a given finite set, but this is a very inefficient way to do that. Indeed, given some k-combination it is much easier to find the next combination in lexicographic ordering directly than to convert a number to a k-combination by the method indicated above. To find the next combination, find the smallest i ≥ 2 for which c_i ≥ c_i−1+2 (if there is no such i, take i = k+1); then increase c_i−1 by one and set all c_j with j < i − 1 to their minimal value j − 1. If the k-combination is represented by its characteristic vector, that is as a binary value with k bits 1, then the next such value can be computed without any loop using bitwise arithmetic: the following function will advance x to that value or return false:

// find next k-combination bool next_combination(unsigned long& x) // assume x has form x'01^a10^b in binary { unsigned long u = x & -x; // extract rightmost bit 1; u = 0'00^a10^b unsigned long v = u + x; // set last non-trailing bit 0, and clear to the right; v=x'10^a00^b if (v==0) // then overflow in v, or x==0 return false; // signal that next k-combination cannot be represented x = v +(((v^x)/u)>>2); // v^x = 0'11^a10^b, (v^x)/u = 0'0^b1^{a+2}, and x ← x'100^b1^a return true; // successful completion }

This is called Gosper's hack; corresponding assembly code was described as item 175 in HAKMEM.

On the other hand the possibility to directly generate the k-combination at index N has useful applications. Notably, it allows generating a random k-combination of an n-element set using a random integer N with, simply by converting that number to the corresponding k-combination. If a computer program needs to maintain a table with information about every k-combination of a given finite set, the computation of the index N associated to a combination will allow the table to be accessed without searching.