Context: I'm working on this problem:There are two stacks here:A: 1,2,3,4 <- Stack Top  B: 5,6,7,8A and B will pop out to other two stacks: C and D. For example:  pop(A),push(C),pop(B),push(D).If an item have been popped out , it must be pushed to C or D immediately.The goal is to enumerate all possible stack contents of C and D after moving all elements.More elaborately, the problem is this: If you have two source stacks with $n$ unique elements (all are unique, not just per stack) and two destination stacks and you pop everything off each source stack to each destination stack, generate all unique destination stacks - call this $S$.The stack part is irrelevant, mostly, other than it enforces a partial order on the result. If we have two source stacks and one destination stack, this is the same as generating all permutations without repetitions for a set of $2N$ elements with $N$ 'A' elements and $N$ 'B' elements. Call this $O$.Thus$\qquad \displaystyle |O| = (2n)!/(n!)^2$Now observe all possible bit sequences of length 2n (bit 0 representing popping source stack A/B and bit 1 pushing to destination stack C/D), call this B. |B|=22n. We can surely generate B and check if it has the correct number of pops from each destination stack to generate |S|. It's a little faster to recursively generate these to ensure their validity. It's even faster still to generate B and O and then simulate, but it still has the issue of needing to check for duplicates.My questionIs there a more efficient way to generate these?Through simulation I found the result follows this sequence which is related to Delannoy Numbers, which I know very little about if this suggests anything.Here is my Python codedef all_subsets(list):    if len(list)==0:        return [set()]    subsets = all_subsets(list[1:])    return [subset.union(set([list[0]])) for subset in subsets] + subsetsdef result_sequences(perms):    for perm in perms:        whole_s = range(len(perm))        whole_set = set(whole_s)        for send_to_c in all_subsets(whole_s):            send_to_d = whole_set-set(send_to_c)            yield [perm,send_to_c,send_to_d]n = 4perms_ = list(unique_permutations([n,n],['a','b'])) # number of unique sequences                                                                                                               result = list(result_sequences(perms_))
Generating number of possibilites of popping two stacks to two other stacks
algorithms;combinatorics;efficiency
(answer for another problem, see the edit below)First, generate all subsets $A_1$ of $A$. $A_1$ will go in $C$ and $A_2=A\backslash A_1$ in $D$. Likewise, generate all subsets $B_1$ of $B$. You then have to generate all possible ordered combinations of $A_1$ and $B_1$ for $C$ and the same for $A_2$ and $B_2$ in $D$.This amounts to enumerate, given $(a_1,,a_n)$ and $(b_1,,b_m)$ all interleavings of length $n+m$ which can be viewed as an exploration of the intersections of a grid of size $nm$. (There are $\frac{(n+m)!}{n!m!}$ paths)This is a way of generating all possible $C$s and $D$s uniquely.But maybe I misunderstood the question. Is this what you want? To help comparing with what you already have tried, here is the number of pairs of stacks it generates (where $A$ is the size of $A$):$$N(A,B)=\sum_{n=0}^{A}\sum_{m=0}^{B}\binom{A}{n}\binom{B}{m}\frac{(n+m)!}{n!m!}\frac{(A+B-n-m)!}{(A-n)!(B-m)!}$$Formula when $A=B$ on the OEIS.Implementation in HaskellExecution trace for A=[a, b] B=[1, 2] with 54 pairs since $N(2,2)=54$EDIT: I am wrong: my algorithm behaves like separating $A$ and $B$ into $(A_1,A_2)$ and $(B_1,B_2)$ before interleaving $(A_1,B_1)$ and $(A_2,B_2)$ which is presumably what you don't want (it generates too many stacks, e.g. from $A=[2,1], B=[4,3]$ it includes $C=[2,3],D=[4,1]$). (Mitchus's answer does not have this problem.)