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

ignougroup
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=Abackslash 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)!}$$

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