iterating over subsets by switching one element at a time

Question

How do I iterate over all the $k$-element subsets of $\{1,2,\dots, n\}$ by switching one element at a time?

123
134
234
124
145
245
345
135
235
125

This comes from Ch2 of Combinatorial Algorithms by Nienhuis and Wilf.

Equivalently I am asking for a Hamiltonian circuit on the Johnson graph of $k$ element subsets of a set of $n$ elements connected if their intersection has $k-1$ elements.

---

I am trying to understand how the equation $$A(n,k) = A(n-1,k), \overline{ A(n-1,k-1)}\otimes \{n\}$$ from Nienhuis-Wilf leads to a type of "gray code" for subsets. In fact, it is the gray code when you restruct to $k$-element sets.

Here, $A(n,k)$ is an ordering, looping over the $k$-element subsets of $\{1,2,\dots, n\}$. The notation $\overline{ A(n-1,k-1)}\otimes \{n\}$ means we should list the $k-1$-element substs of $\{1,2,\dots, n-1\}$ and append the element $n$ to each element of that list.

This equation can also be thought of a set theoretic version of the binomial coefficient identity

$$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$

Using this formation I came up a means of listing all the subsets in order.

Here gc(n,k) is returning an array of $k$-element arrays, enumerating the $k$-element subsets of $\{1,2,\dots, n\}$.

def gc(n,k):
    if(k==1):
        return [[i+1] for i in range(n)]
    elif(n == 0):
        return []
    else:
        L = [ x+ [n] for x in gc(n-1,k-1)]
        return gc(n-1,k)+ L[::-1]

How do I find the predecessor or successor of a given subset without generating all the subsets? I wrote some python code for this, which is different from what is in the textbook. It still doesn't return the correct answer.

def S(n,k,a):
    if k == 1:
        return [(a[0] + 1)%n]
    elif(a[-1] == n-1):
        return P(n-1,k-1, a[:-1]) + [n-1]
    else:
        return S(n-1,k,a)

def P(n,k,a):
    if k == 1:
        return [(a[0] - 1)%n]
    elif(a[-1] == n-1):
        return S(n-1,k-1, a[:-1]) + [n-1]
    else:
        return P(n-1,k,a)

This looks pretty close to the recursion in Nienhuis-Wilf but I would like to understand where I am going wrong in my implementation.

Answer 1

Here is how to convert a number from $\binom{n}{k}$ to a subset of $\binom{[n]}{k}$, and vice versa. This is known as inductive counting. I'll use your formula $$ \binom{[n]}{k} = \binom{[n-1]}{k} + \binom{[n-1]}{k-1} \times \{n\}. $$

Given a code $x \in [0,\binom{n}{k})$, the idea is that the first $\binom{n-1}{k}$ codes will be used to code the $\binom{[n-1]}{k}$ part, and the rest will be used to code a subset in $\binom{[n-1]}{k-1}$ which will be completed to the required subset by adding the element $n$. Here is the relevant quasi-python code:

decode(n, k, code):
  if k == 0:
    return []
  elif code < binom(n-1, k):
    return decode(n-1, k, code)
  elif:
    return decode(n-1, k-1, code - binom(n-1, k)) + [n-1]

Encoding is the reverse process, and mirrors it exactly:

  encode(n, k, S):
    if k == 0:
      return 0
    elif n-1 not in S:
      return encode(n-1, k, S)
    else:
      return encode(n-1, k-1, S[:-1]) + binom(n-1, k)

Using these subroutines, you can compute the successor and predecessor of a given subset. You could also do it directly, for example by "unrolling" the resulting code, but this is a programming question which you should be able to solve for yourself in a couple hours.

---

The preceding doesn't produce a Gray code at all. You can obtain a Gray code by reversing the second half in your fundamental formula (this is the meaning of the overline). The corresponding decoding function is

decode2(n, k, code):
  if k == 0:
    return []
  elif code < binom(n-1, k):
    return decode2(n-1, k, code)
  elif:
    return decode2(n-1, k-1, binom(n, k) - 1 - code) + [n-1]

I'll leave the encoding function as an exercise. The proof that this forms a Gray code is by induction. You prove a more general claim, stating what are the first and last sets in the ordering for any given $n,k$, and given that you prove by induction that the result is a Gray code. Details left to you.