de.christofreichardt.scala.combinations

Produces all combinations of k unordered integers which can be chosen from among n integers (k <= n) by applying a lexicographic algorithm. The starting point is given by the lexicographic smallest word comprising k integers, e.g. (0,1,2) for k == 3. First, the algorithm evaluates the rightmost column in order to find new combinations, e.g. (0,1,3), (0,1,4) and (0,1,5) for n == 6. Now the algorithm has run out of options for the rightmost column and switches to (0,2,3) but not (0,2,1) since the latter would be identical to (0,1,2). In due course more to the left columns have to be considered, e.g. at (0,4,5). The algorithm finishes if the options have run out for all columns. For k == 3 and n == 6 that would be (3,4,5). The total number of solutions is given by the binomial coefficient "n choose k". For the given example that would be 20. To compute actual solution sizes , see WolframAlpha.

Produces all combinations from 'n choose 0' up to 'n choose n', that is the total number of the to be produced combinations can be read from the nth line of Pascal's triangle.