On-demand algorithm to return successive combinations of k elements from n

Question

This post shows how to write an algorithm to spit out, at one time, all combinations of k elements from n, avoiding permutations. But how would one write an algorithm that, on demand, gives the next combination (obviously, without precomputing and storing them)? It would be initialized with the ordered set of symbols n and an integer k, and would then be called to return the next combination.

Pseudocode or a good English narrative would be fine for my purposes - I'm not fluent in much beyond Perl and C and a bit of Java.

Answer 1

ORIGINAL WORDING

(SKIP TO THE UPDATE BELOW)

---

1. Let's assume that the n elements are the integers 1..n.
2. Represent every k-combination in increasing order (this representation gets rid of permutations inside the k-combination.)
3. Now consider the lexicographic order between k-combinations (of n elements). In other words, {i_1..i_k} < {j_1..j_k} if there exists an index t such that
   • i_s = j_s for all s < t and
   • i_t < j_t.
4. If {i_1..i_k} is a k-combination, define next{i_1..i_k} to be the next element w.r.t. the lexicographic order.

Here is how to compute next{i_1..i_k}:

• Find the largest index r such that i_r + 1 < i_{r+1}
• If no index satisfies this condition and i_k < n, set r := k
• If none of the above conditions can be satisfied, there is no next (and the k-combination equals {n-k+1, n-k+2,... ,n})
• If r satisfies the first condition, set next to be {i_1, ..., i_{r-1}, i_r + 1, i_{r+1}, ..., i_k}
• If r = k (second condition), set next := {i_1, ..., i_{k-1}, i_k + 1}.

---

UPDATE (Many thanks to @rici for improving the solution)

1. Let's assume that the n elements are the integers 1..n.
2. Represent every k-combination in increasing order (this representation gets rid of permutations inside the k-combination.)
3. Now consider the lexicographic order between k-combinations (of n elements). In other words, {i_1..i_k} < {j_1..j_k} if there exists an index t such that
   • i_s = j_s for all s < t and
   • i_t < j_t.
4. If {i_1..i_k} is a k-combination, define next{i_1..i_k} to be the next element w.r.t. the lexicographic order.
5. Note that with this order the smallest k-combination is {1..k} and the largest {n-k+1, n-k+2,... ,n}.

Here is how to compute next{i_1..i_k}

• Find the largest index r such that i_r can be incremented by 1.
• Increment the value at index r and reset the following elements with consecutive values starting at i_r + 2.
• Repeat until no position can be incremented.

More precisely:

• If i_k < n, increment i_k by 1 (i.e., replace i_k with i_k + 1)
• If i_k = n, find the largest index r such that i_r + 1 < i_{r+1}. Then increment i_r by 1 and reset the following positions to {i_r + 2, i_r + 3, ..., i_r + k + 1 - r}
• Repeat until you reach {n-k+1, n-k+2,... ,n}

Note the recursive character of the algorithm: every time it increments the least significant position the tail is reset to the lexicographically smallest sequence that starts with the value just incremented.

---

Smalltalk code

SequenceableCollection >> #nextChoiceFrom: n
    | next k r ar |
    k := self size.
    (self at: 1) = (n - k + 1) ifTrue: [^nil].
    next := self shallowCopy.
    r := (self at: k) = n
      ifTrue: [(1 to: k-1) findLast: [:i | (self at: i) + 1 < (self at: i+1)]]
      ifFalse: [k].
    ar := self at: r.
    r to: k do: [:i | 
      ar := ar + 1.
      next at: i put: ar].
    ^next

Answer 2

Here's a prose description of how to do this. Start with your favorite iterative algorithm for generating all combinations. Then turn each loop variable into a state variable, and package it all into a class. Construct an instance of the class with k and n and initialize each state variable according to the algorithm.

Answer 3

You can implement most of these algorithms as you've described by converting them to an Iterator Pattern. This requires you to save the state of the algorithm between successive nextELement() calls.

If your language has support for coroutines, you may be able to convert the code more easily. Python and C# both have a yield keyword that can be used to transfer control back to the calling function while retaining the state of algorithm you're executing.