Unique combination of sets We start with a finite number of $N$ sets, $\boldsymbol{X}_1,\ldots,\boldsymbol{X}_N$, each containing a finite number of integers. The sets do not in general have the same number of elements. The goal is to find all possible unique combination that you can get by taking the union of some of these sets. All sets need to be used.
Example for $N = 4$ the possible combinations are:


*

*$\boldsymbol{X}_1,\boldsymbol{X}_2,\boldsymbol{X}_3, \boldsymbol{X}_4$

*($\boldsymbol{X}_1\bigcup\boldsymbol{X}_2),\boldsymbol{X}_3, \boldsymbol{X}_4$

*($\boldsymbol{X}_1\bigcup\boldsymbol{X}_2),(\boldsymbol{X}_3 \bigcup\boldsymbol{X}_4)$

*$\boldsymbol{X}_1,\boldsymbol{X}_2,(\boldsymbol{X}_3 \bigcup\boldsymbol{X}_4)$

*($\boldsymbol{X}_1\bigcup\boldsymbol{X}_3),\boldsymbol{X}_2,\boldsymbol{X}_4$

*($\boldsymbol{X}_1\bigcup\boldsymbol{X}_3),(\boldsymbol{X}_2\bigcup\boldsymbol{X}_4)$

*$\boldsymbol{X}_1,\boldsymbol{X}_3,(\boldsymbol{X}_2\bigcup\boldsymbol{X}_4)$

*($\boldsymbol{X}_1\bigcup\boldsymbol{X}_4),\boldsymbol{X}_2,\boldsymbol{X}_3$

*($\boldsymbol{X}_1\bigcup\boldsymbol{X}_4),(\boldsymbol{X}_2\bigcup\boldsymbol{X}_3)$

*$\boldsymbol{X}_1,\boldsymbol{X}_4,(\boldsymbol{X}_2\bigcup\boldsymbol{X}_3)$

*($\boldsymbol{X}_1\bigcup\boldsymbol{X}_2\bigcup\boldsymbol{X}_3),\boldsymbol{X}_4$

*($\boldsymbol{X}_1\bigcup\boldsymbol{X}_2\bigcup\boldsymbol{X}_4),\boldsymbol{X}_3$

*($\boldsymbol{X}_1\bigcup\boldsymbol{X}_3\bigcup\boldsymbol{X}_4),\boldsymbol{X}_2$

*$\boldsymbol{X}_1,(\boldsymbol{X}_2\bigcup\boldsymbol{X}_3\bigcup\boldsymbol{X}_1)$

*($\boldsymbol{X}_1\bigcup\boldsymbol{X}_2\bigcup\boldsymbol{X}_3\bigcup\boldsymbol{X}_1$)


This could be encoded in a matrix as:
$\begin{bmatrix}0,0,0,0\\1,1,0,0\\1,1,2,2\\0,0,1,1\\1,0,1,0\\1,2,1,2\\0,1,0,1\\1,0,0,1\\1,2,2,1\\0,1,1,0\\1,1,1,0\\1,1,0,1\\1,0,1,1\\0,1,1,1\\1,1,1,1\end{bmatrix}$,
where each column corresponds with a set and each row with a combination; a $0$ indicates that the set is not combined with any other set and $1$, $2$, etc. indicates a union of the sets with the same number.
How do I generate this sequence in general (for my particular application I expect $N<20$). Can anyone point me in the right direction? 
 A: First pick where the zeros go. This may be either in every space, or leave at least two spaces. Now for the 1's, assuming there are $r\ge 2$ spaces left at this point. You must place a 1 in the first nonempty space, and there need to be at least two 1's. The only other requirement is that at this stage of putting 1's in you either fill up all the presently open stages, or leave at least two spaces fror the 2's at the next stage.
It shoud be clear now: Just before putting the $k$'s in (if you get that far) there are at least two empty spots. You now must place a $k$ in the leftmost empty spot, must place at least two $k$'s, and the only othe restriction is that either you fill all the remaining spaces with $k$'s, or else leave at least two spaces for the next step when the $k+1$ values are to be filled in.
Of course one has to store all the as yet unfinished strings. (Maybe this is "exponential space" requirement.) Note that one must at each stage put the present digit in the leftmost available space, in order to avoid making two strings meaning the same thing. Also natural is that (after placing the 0's which mean singleton sets) at any stage one must place at least two, in order to avoid making another singleton. And if one doesn't finish at that stage one must leave at least two spots for the next stage.
It seems likely that the number of strings to deal with for length 20 might be too large to deal with. I'd try it for some smaller numbers first to get an idea, so as to avoid crashing the computer.
Added note The total number of ways for $n$ is called the Bell number of $n$. There's some things known about this, including some methods of generating them. See here. In a followup page linked from there is a table, and the total number of such sequences in case $n=20$ is over $51$ trillion. 
A: I would generate the partitions of $N$.  For $4$, they are $4, 3+1, 2+2, 2+1+1, 1+1+1+1$, then assign that many sets to each partition.  The $4$ corresponds to your combination $15$.  For $3+1$ there are four ways to choose the $3$, giving your combinations $11,12,13,14$.  When you have multiple partitions of the same size, you need some way not to repeat, like saying the lowest number set in any of those is in the first partition.  Then $2+2$ gives $3,6,9$ and so on.
