Recursively generating all partitions

Question

Given a set $\{1,2,\ldots,n\}$, I would like to recursively generate all partition of size $r$ and $n-r$. For instance, we start with the partitions $$\{1,2,\ldots, r\} \quad \{r+1,\ldots, n\}$$ and then iteratively swap elements. We can write the solution in terms of all the collections of allowed swaps between the two sets. We do this by considering a swap operator $S_{ij}$, which swaps elements $i$, $j$ between these sets, for instance:

$$S_{1,r+1} \{\{1,2,\ldots, r\},\{r+1,\ldots, n\}\} = \{\{r+1,2,3,\ldots, r\},\{1, r+2,\ldots, n\}\}.$$

Then we can write the solution in terms of all $\binom{n}{r}$ strings of swap operators acting on the two sets.

---

I know that one way to do this is with Heap's algorithm, which would generate all the permutations, which we then just have to partition. However, this algorithm is inefficient for this problem since many permutations correspond to the same subsets. As such I am essentially looking for a simplification to Heap's algorithm for this specific case.

Answer 1

You need to generate all the $r$ sized subsets, of which there are $n \choose r$. ${n-1 \choose r-1}$ of them contain $1$ and ${n-1 \choose r}$ do not contain $1$, so call your subset generator program with those parameters, add $1$ to each set in the output of the first instance, and put them together.

Answer 2

I believe the answer to the question is merely all sets $$\{\{i_1,i_2,\ldots i_r\}, \{\text{rest of the set}\}\}$$ where $i_r \in \{r,r+1,\ldots, n\}$, $i_{r-1} \in \{r-1,\ldots,i_r - 1\}$,..., $i_1 \in \{1,\ldots, i_2-1\}$. One way to easily generate this is by swapping elements of an ordered list (tuples). All tuples are generated by permutations $$\forall_{i_r = r}^{n} \forall_{i_{r-1}}^{i_r-1} \cdots \forall_{i_1 = 1}^{i_2 - 1} P_{r,i_r} P_{r-1,i_{r-1}}\cdots P_{2,i_2} P_{1,i_1} (1,\ldots r,r+1,\ldots n),$$ where $P_{ij}$ swaps the $i$ and $j$th element. Splitting the all these tuples then at the $r$th element yields all $\binom{n}{r}$ partitions exactly once.

I have checked numerically that this indeed works. A more formal mathematical prove would just use the fact that the way we choose the $i$'s, generates all ordered lists of size $r$ from $n$ elements. Combining this with the "rest" of the set, yields all partitions.