[Solved]: Generating number of possibilites of popping two stacks to two other stacks

Problem Detail: 

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_)) 

Asked By : dfb

Answered By : jmad

(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.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2257