Algorithm to return all combinations of k elements from n

Much of the content in The Art of Computer Programming Volume 4: Volume 3 may be better suited to your particular situation than my description.

Gray code

One problem you'll have is memory of course, and soon enough, you'll have problems with 20 elements in your set - ²⁰ C ₃ = 1140. And if you're iterating over the collection, it's better to use a modified gray-code algorithm, so you don't have to keep all the code in memory. These will generate the next combination based on the previous one and avoid repetition. Many of them are used for different purposes. Do we want to maximize the difference between consecutive combinations? minimize? and many more.

Some original papers describing Gray codes:

1. Certain Hamiltonian Paths and Least Change Algorithms
2. Algorithm for Combination Generation of Adjacent Interchange

Here are some other papers covering the topic:

1. Eades, Hickey, Read Efficient Implementation of Adjacent Interchange Combination Generation Algorithm (PDF, with code in Pascal)
2. Combined generator
3. Combined Gray Code Survey (PostScript)
4. Gray code algorithm

Chase's Violin (Algorithms)

Phillip J Chase, " Algorithm 382: Combinations of M of N Objects " (1970)

Algorithms in C ...

Combined indexing in lexicographical order (Buckles Algorithm 515)

You can also reference combinations by their combination index (lexicographically). Realizing that the index should be based on some change in the index from right to left, we can construct something that should restore the composition.

So we have a set of {1,2,3,4,5,6}... and we want three elements. Assuming {1,2,3}, we can say that the difference between the elements is 1 and the order is the smallest. There is a variation of {1,2,4} which is lexicographically the number 2. So the number of "changes" in the last bit accounts for a change in lexicographical order. The second position that changed {1,3,4} has one change, but since it is in the second position (proportional to the number of elements in the original set), it accounts for more change.

The approach I've described seems to be a deconstruction, from setting to indexing, we need to do the opposite - which is much more complicated. This is how the buckle solves the problem. I wrote some C to compute them , with a slight twist - I used the index of the set to represent the set instead of a range of numbers, so we always start at 0...n. Notice:

1. Since the combinations are unordered, {1,3,2} = {1,2,3} - we sort them lexicographically.
2. This method has an implicit 0 to start the collection of the first difference.

Lexicographically Combining Indexes (McCaffrey)

There is another way : , its concept is easier to grasp and program, but Buckles are not optimized. Fortunately, it also doesn't produce duplicate combinations:

maximized set , where .

For example: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1). So the 27th dictionary combination for the fourth thing is: {1,2,5,6}, these are the indices of whatever collection you want to look at. The following example (OCaml) requires choosefunctions and is left to the reader:

(* this will find the [x] combination of a [set] list when taking [k] elements *)
let combination_maccaffery set k x =
    (* maximize function -- maximize a that is aCb              *)
    (* return largest c where c < i and choose(c,i) <= z        *)
    let rec maximize a b x =
        if (choose a b ) <= x then a else maximize (a-1) b x
    in
    let rec iterate n x i = match i with
        | 0 -> []
        | i ->
            let max = maximize n i x in
            max :: iterate n (x - (choose max i)) (i-1)
    in
    if x < 0 then failwith "errors" else
    let idxs =  iterate (List.length set) x k in
    List.map (List.nth set) (List.sort (-) idxs)

A simple combinatorial iterator

For teaching purposes, the following two algorithms are provided. They implement the overall combination of iterators and (more general) folders. They are as fast as possible, with complexity O( ⁿ C _k ). Memory consumption is constrained k.

We'll start with an iterator that will call a user-provided function for each combination

let iter_combs n k f =
  let rec iter v s j =
    if j = k then f v
    else for i = s to n - 1 do iter (i::v) (i+1) (j+1) done in
  iter [] 0 0

Starting from an initial state, a more general version will call user-provided functions along with state variables. Since we need to pass states between different states, we won't use a for loop, but recursion,

let fold_combs n k f x =
  let rec loop i s c x =
    if i < n then
      loop (i+1) s c @@
      let c = i::c and s = s + 1 and i = i + 1 in
      if s < k then loop i s c x else f c x
    else x in
  loop 0 0 [] x