Suppose we have a set composed of elements. Our goal is to list all the possible ways in which we can choose elements in a lexicographical order. Intuitively speaking, we want to postpone as long as possible the selection of elements with larger indices.

The total number of combinations is given by the binomial coefficient . For example, if we have a set of elements , we know that we can choose elements in 10 different ways. If we create a characteristic vector where the element is selected if and only if the j-th entry of the characteristic vector is 1, then the lexicographic listing of the combinations would look like:

00111
01011
01101
01110
10011
10101
10110
11001
11010
11100

Informally speaking (very informally…), the lexicographical listing algorithm moves the rightmost 1 to the left as long as there is “space” (i.e. there is a zero to the left), otherwise the rightmost 1 preceded by a 0 is moved to its left and all the remaining 1s are all pushed to the right. This algorithm is formally described and analyzed in the paper “Producing Permutations and Combinations in Lexicographical Order” by professor Alon Itai. The beauty of this non recursive algorithm is that it does not require to generate all the combinations beforehand: instead they can be generated on demand using the previous combination (we only have to maintain two counters).

I implemented this algorithm in Matlab/Octave and it is available as a gist:

I also included a small test program that illustrates the use of the next_combination function. It generates a binary image where the j-th row corresponds to the characteristic vector of the r-th combination for and :

The j-th row of the image displays the characteristic vector for the j-th combination of 5 elements selected from a set of 9 elements.