1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What have you tried? We're not here to solve your exercise for you, but if you've made a serious effort and if you show us what you've tried so far and where you got stuck, the question might be suitable for this site. If you haven't made a serious effort so far, it's probably premature to ask. For instance, have you tried some small examples (for various small values of $k$ and $n$)? $\endgroup$ – D.W. Jan 5 '14 at 3:53
  • $\begingroup$ @D.W. Other than lexicographic order, which doesn't switch 1 element at time at certain places anyway. The same chapter explains this confusing "Revolving Door" algorithm. There may be other ways, so I am asking on here. $\endgroup$ – john mangual Jan 5 '14 at 3:57
  • $\begingroup$ Check out Knuth's new volume, which has algorithms of this kind. $\endgroup$ – Yuval Filmus Jan 5 '14 at 7:54
  • 1
    $\begingroup$ This is a dump of a homework/exercise problem, not a question. If you have a specific question regarding the wording of the problem or about concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See also here for our homework policy, and here for a relevant discussion. $\endgroup$ – Raphael Jan 5 '14 at 17:01
  • $\begingroup$ @D.W. Here is what I have done so far... I am reading a paper where a set requires me to iterate over subsets and evaluate a certain function. $\endgroup$ – john mangual Jan 5 '14 at 17:25
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.