<p>This isn't a solution so much as it's another way to think about the problem.</p>

<p>Make the following graph: </p>

<ul>
<li>Vertices are all subsets of <code>S</code> of sizes <code>n</code> or <code>n+1</code>. </li>
<li>There is an edge between <code>v</code> and <code>w</code> if the two sets differ by one element.</li>
</ul>

<p>For example, for n=1, you get the following cycle:</p>

<pre><code> {1} --- {1,3} --- {3}
  |                 |
  |                 |
{1,2} --- {2} --- {2,3}
</code></pre>

<p>Your problem is to find a <a href="http://en.wikipedia.org/wiki/Hamiltonian_path" rel="nofollow">Hamiltonian cycle</a>:</p>

<blockquote>
  <p>A Hamiltonian cycle (or Hamiltonian circuit) is a cycle in an
  undirected graph which visits each vertex exactly once and also
  returns to the starting vertex. Determining whether such paths and
  cycles exist in graphs is the Hamiltonian path problem which is
  NP-complete.</p>
</blockquote>

<p>In other words, this problem is hard.</p>

<p>There are a handful of theorems giving sufficient conditions for a Hamiltonian cycle to exist in a graph (e.g. if all vertices have degree at least <code>N/2</code> where <code>N</code> is the number of vertices), but none that I know immediately implies that this graph has a Hamiltonian cycle.</p>

<p>You could try one of the myriad algorithms to determine if a Hamiltonian cycle exists. For example, from the wikipedia article on the <a href="http://en.wikipedia.org/wiki/Hamiltonian_path_problem" rel="nofollow">Hamiltonian path problem</a>:</p>

<blockquote>
  <p>A trivial heuristic algorithm for locating hamiltonian paths is to
  construct a path abc... and extend it until no longer possible; when
  the path abc...xyz cannot be extended any longer because all
  neighbours of z already lie in the path, one goes back one step,
  removing the edge yz and extending the path with a different neighbour
  of y; if no choice produces a hamiltonian path, then one takes a
  further step back, removing the edge xy and extending the path with a
  different neighbour of x, and so on. This algorithm will certainly
  find an hamiltonian path (if any) but it runs in exponential time.</p>
</blockquote>

<p>Hope this helps.</p>

<hr>

<p><strong>Good News</strong>: Though the Hamiltonian cycle problem is difficult in general, this graph is very nice: it's bipartite and <code>(n+1)</code>-regular. This means there may be a nice solution for this particular graph.</p>

<p><strong>Bad News</strong>: After doing a bit of searching, it turns out that this problem is known as the <em>Middle Levels Conjecture</em>, and it seems to have originated around 1980. As best I can tell, the problem is still open in general, but it has been computer verified for <code>n &lt;= 17</code> (and I found a <a href="http://arxiv.org/abs/0912.4564" rel="nofollow">preprint</a> from 12/2009 claiming to verify <code>n=18</code>). These two pages have additional information about the problem and references:</p>

<ul>
<li><a href="http://www.math.uiuc.edu/~west/openp/revolving.html" rel="nofollow">http://www.math.uiuc.edu/~west/openp/revolving.html</a></li>
<li><a href="http://garden.irmacs.sfu.ca/?q=op/middle_levels_problem" rel="nofollow">http://garden.irmacs.sfu.ca/?q=op/middle_levels_problem</a></li>
</ul>
Write a function to cycle through subsets by adding/deleting elements
<p>Problem: Start with a set <code>S</code> of size 2n+1 and a subset <code>A</code> of <code>S</code> of size n. You have functions <code>addElement(A,x)</code> and <code>removeElement(A,x)</code> that can add or remove an element of <code>A</code>. Write a function that cycles through all the subsets of <code>S</code> of size n or n+1 using just these two operations on <code>A</code>.</p>

<p>I figured out that there are (2n+1 choose n) + (2n+1 choose n+1) = 2 * (2n+1 choose n) subsets that I need to find. So here's the structure for my function:</p>

<pre><code>for (int k=0; k&lt;2*binomial(2n+1,n); ++k) {
    if (k mod 2) {
        // somehow choose x from S-A
        A = addElement(A,x);
        printSet(A,n+1);
    } else
        // somehow choose x from A
        A = removeElement(A,x);
        printSet(A,n);
    }
}
</code></pre>

<p>The function <code>binomial(2n+1,n)</code> just gives the binomial coefficient, and the function <code>printSet</code> prints the elements of <code>A</code> so that I can see if I hit all the sets.</p>

<p>I don't know how to choose the element to add or remove, though. I tried lots of different things, but I didn't get anything that worked in general.</p>

<p>For n=1, here's a solution that I found that works:</p>

<pre><code>for (int k=0; k&lt;6; ++k) {
    if (k mod 2) {
        x = S[A[0] mod 3];
        A = addElement(A,x);
        printSet(A,2);
    } else
        x = A[0];
        A = removeElement(A,x);
        printSet(A,1);
    }
}
</code></pre>

<p>and the output for <code>S = [1,2,3]</code> and <code>A=[1]</code> is:</p>

<pre><code>[1,2]
[2]
[2,3]
[3]
[3,1]
[1]
</code></pre>

<p>But even getting this to work for n=2 I can't do. Can someone give me some help on this one?</p>