Let $S$ be the set of all $k$-element subsets of some given universe $M$. My question is as follows: Is it possible to enumerate (without repetition) the elements of $S$ such that each pair of consecutive sets differ in 2 elements.

I've been thinking about the following approaches, but so far haven't made much progress:

We can think of the sets in $S$ as binary vectors of length |M|, where the vector for set $A$ is 1 at index $i$ iff the $i$-th element of $M$ is in $A$. We can form a graph by using these vectors as vertices and where there is an edge between $2$ vertices if their Hamming distance is exactly $2$. Now the goal becomes finding a Hamiltonian path in this graph.

  • $\begingroup$ Apologies, yes you're right, Grey codes only solve the problem for $k+1$ and $k-1$ subsets. I'm interested in the case where all sets have size $k$. (I've added a clarification.) $\endgroup$ Nov 18 '14 at 18:26
  • $\begingroup$ @HughDenoncourt, When you say “the subsets 123 and 124 [the codes $11100$ and $11010$ represent] are 1 apart,” I don’t think you are using the idea of “differing” in a way that’s related to the question. The sets $\{1,2,3\}$ and $\{1,2,4\}$ “differ” as to whether they contain (or don’t) two elements, 3 and 4. Your notion of difference has to do with the number of changes you need to make to a listing of elements of each set in increasing order. That might be interesting, but it might not be useful here. (How far apart would you consider the sets $\{1,2,3\}$ and $\{2,3,4\}$, by the way? $\endgroup$
    – Steve Kass
    Nov 18 '14 at 18:43
  • $\begingroup$ @Hugh, Thanks. Yes, the Hamming distance of the strings $123$ and $234$ is $3$. The question I asked was “How far apart would you consider the subsets $\{1,2,3\}$ and $\{2,3,4\}$?” Those subsets should be a distance of 2 apart for the original question. So if you consider them distance 3 apart, these strings (list the subset elements in lexicographic order) won't be helpful to the original question. Hamming distance for these lexicographic strings measures something different than the distance in this MSE question. That’s not to say the strings you describe aren’t useful in other situations. $\endgroup$
    – Steve Kass
    Nov 18 '14 at 20:51

According to the claim after Lemma 1.1 in this paper, the answer is yes. Take the $k$-subsets in the order they appear in the (reflected) Gray code for the full power set of $M$.


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.