9.29

Idea. Store the current combination in an array a[0‥k-1] holding the indices of the chosen items (0-based). The first subset is (0,1,…,k-1). To obtain the next subset lexicographically: 1. Scan a from the right while a[i] = n-k+i. 2. Let this stopping position be i. Increment a[i] by 1. 3. Reset the tail so that a[j] = a[j-1]+1 for all j > i. Repeating these steps outputs every [math]\binom{n}{k}[/math] subset exactly once, in O(k) time and O(k) memory per subset. Complexities: total time O([math]\binom{n}{k}k[/math]), extra space O(k).

Pseudocode
function combinations(n, k):
  a ← [0, 1, …, k-1]
  yield a
  while true:
    /* step 1 */
    i ← k-1
    while i ≥ 0 and a[i] = n-k+i:
      i ← i-1
    if i < 0: return /* finished */
    /* step 2 */
    a[i] ← a[i]+1
    /* step 3 */
    for j from i+1 to k-1:
      a[j] ← a[j-1]+1
    yield a

Python snippet
def combinations(iterable, k):
  items = list(iterable)
  n = len(items)
  idx = list(range(k))
  yield [items[i] for i in idx]
  while True:
    for i in range(k-1,-1,-1):
      if idx[i] != n-k+i: break
    else:
      return
    idx[i] += 1
    for j in range(i+1, k):
      idx[j] = idx[j-1] + 1
    yield [items[t] for t in idx]

Usage example (prints all 3-subsets of {0,…,4}):
for c in combinations(range(5), 3):
  print(c)
Output: [0,1,2] [0,1,3] [0,1,4] [0,2,3] [0,2,4] [0,3,4] [1,2,3] [1,2,4] [1,3,4] [2,3,4]

Back to Chapter 9