Generating number of possibilites of popping two stacks to two other stacks

Question

Context: I'm working on this problem:

There are two stacks here:

A: 1,2,3,4 <- Stack Top
  B: 5,6,7,8

A 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 question

Is 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 code

def all_subsets(list):
    if len(list)==0:
        return [set()]
    subsets = all_subsets(list[1:])

    return [subset.union(set([list[0]])) for subset in subsets] + subsets

def 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 = 4
perms_ = list(unique_permutations([n,n],['a','b'])) # number of unique sequences                                                                                                               
result = list(result_sequences(perms_))

Answer 1

(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 $n×m$. (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 Haskell
• Execution 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.)

Answer 2

It seems to me that an efficient way to enumerate those sequences is simply by constructing all possible stacks recursively. See Python example below (n.b. my stacks have the top on the right-hand side).

def enumerate_stacks(A, B, C=[], D=[], seq=[]):
    if len(A)+len(B) == 0:
        print seq, C, D
    else:
        if len(A)>0:
            enumerate_stacks(A[1:], B,     [A[0]]+C, D       , seq + [0,0])
            enumerate_stacks(A[1:], B,     C,        [A[0]]+D, seq + [0,1])
        if len(B)>0:
            enumerate_stacks(A,     B[1:], [B[0]]+C, D       , seq + [1,0])
            enumerate_stacks(A,     B[1:], C,        [B[0]]+D, seq + [1,1])

A = [2,1]
B = [4,3]

enumerate_stacks(A,B)