Given $S = \{1, 2, \ldots, n\}$, consider partitions of $S$ of the form $(R, R')$ where $R \subset S$ and $R'$ is $S \setminus R$, the complement of $R$ in $S$. The goal is to list 2-part partitions of $S$ such that


1. the sequence $(Q, Q'), (R, R')$ is allowed in the list if either $Q' \subset R$ or $R \subset Q'$;
2. for each $R \subset S$, exactly one of $(R, R')$ and $(R', R)$ appears in the list; and
3. the list ends with $(S, \emptyset)$ or $(\emptyset, S)$.


Condition 2 means that there are $2^{n-1}$ 2-part partitions in a list. Limited experimentation suggests such a list exists for each $n$. Here is a valid list for $n = 4$:


$$ (4, 123), (12, 34), (3, 124), (24, 13), (1, 234), (2, 134), (14, 23), (\emptyset, 1234).$$


What is a nice inductive procedure or algorithm for creating such a list? It would also be good to know if this a known problem, or equivalent to one.



Finding an inclusion-based path through 2-part set partitions
Here is a construction using [Gray codes](https://en.wikipedia.org/wiki/Gray_code)


Run the standard $n-1$st Gray code backwards, getting all subsets $S\_1$, ..., $S\_{2^{n-1}}=\varnothing$ of $\{1,...,n-1\}$.


Replace each odd-numbered subset with its complement in $\{1,...,n\}$.


1. and 3. are straightforward.
2. follows since (a) for each subset contained in $\{1,...,n-1\}$ we have either it or its complement on our list; (b) this very same argument at the same time says that for each subset *not* contained in $\{1,...,n-1\}$ we have either it or its complement.


