Is there a way to list all partitions of a set by moving one element at a time?

Question

Given a set $S = \{1, 2, \ldots, n\}$, imagine that you start from an initial partition $P^{(0)} = \{P^{(0)}_1, P^{(0)}_2, \ldots\}$ of $S$, then you a create new one $P^{(1)}$ by moving only one element from a block $P^{(0)}_i$ to some other block $P^{(0)}_j$, and so on. You are also allowed to a create a new block, i.e., moves such as $\{\{1, 2, 3\}\} \rightarrow \{\{1, 2\}, \{3\}\}$ are allowed. Is it possible to list all partitions of $S$ in this way, such that no partition repeats in the list?

It's possible when $n=1,2,3$. I don't know for $n=4$. Any help is appreciated!

Illustration for $n=3$:

$$(1)(2)(3) \rightarrow (1,2)(3) \rightarrow (1)(2,3) \rightarrow (1,3)(2) \rightarrow (1, 2, 3)$$

I first moved $1$, then $2$, then $3$ and lastly $2$.

Answer 1

It is possible.

Proof/construction:

Proceed by induction.

Verify directly for small sets.

Given a finite set $S$ of size $n>1$ single out an arbitrary element $s\in S$. Let $f_s$ be the map from $\mathcal P (S)$ to $\mathcal P (S - \{s\})$ obtained by leaving out $s$. Here $\mathcal P$ is the set of partitions.

Then

• $f_s$ is surjective
• the preimage $f_s^{-1}(p)$ of a partition $p \in \mathcal P (S - \{s\})$ can be traversed by moving around $s$
• if $p' \in \mathcal P (S - \{s\})$ is obtained from $p$ by moving a single element $x$ then for any element $P \in f_s^{-1}(p)$ there is a corresponding (though not necessarily unique) move of $x$ that takes $P$ into $f_s^{-1}(p')$

We can therefore "lift" a traversal T of $\mathcal P (S - \{s\})$ to a traversal of $\mathcal P (S)$ by alternating lifting single steps from T with traversing the preimage of the current partition of $S - \{s\}$. $\square$