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 came up withwrote some buggy 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.