Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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_))
share|improve this question
3  
If your output is supposed to be the set of all possible result stacks, the output size alone is exponential. –  Raphael Jun 7 '12 at 22:36
    
@Raphael - I understand this. I'm still looking for the most efficient way to generate these, even if they are asymptotically bound at the same level of complexity –  dfb Jun 8 '12 at 18:32

2 Answers 2

up vote 2 down vote accepted
+100

(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)!}$$

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

share|improve this answer
    
I think this is what I've done in the original problem (see my code in the edit above from SO) except I did it the opposite way - generate interleavings and then use the subsets to assign to stacks. However, my result from simulation and that code above for A,B=4 is 17920, which doesn't seem to jive with your expression above –  dfb Jun 13 '12 at 15:42
    
@dfb oh, sorry: I got the wrong formula for the number of path. I'm much more confident with this one, I tested $N(1,1)=6$ and some cases for $N(3,3)=588$ (the twenty 3-3 interleavings). However $N(4,4)=7110$, I think it is because generating the interleaving before will bring duplicates whereas doing that after won't. –  jmad Jun 13 '12 at 18:04
    
Sorry - I made a mistake too - I wasn't de-duping the simulation. Here's the sequence I get from my simulation: N(1.1)=6 ,N(3.3)=1280,N(2.2)=52,N(4,4)=5136. This matches the integer sequence in the OP. I'll double check my simulation to be sure it doesn't have a bug –  dfb Jun 13 '12 at 18:40
    
PS. I'm considering reflections where given (C,D),(C',D') and C=D', D=C' as two distinct things –  dfb Jun 13 '12 at 18:42
    
My simulation seems ok. I also verified the other answer below by @mitchus produces the same result –  dfb Jun 13 '12 at 23:00

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)
share|improve this answer
    
This is how I approached it in the SO problem, but this generates a large number of duplicates that must be later filtered –  dfb Jun 13 '12 at 15:24
    
What exactly do you mean by duplicates? Identical sequences? Identical resulting stacks? –  mitchus Jun 14 '12 at 7:37
    
Identical resulting stacks –  dfb Jun 14 '12 at 15:00
    
Example N(1,1) - C=[0],D=[1] gets printed twice –  dfb Jun 14 '12 at 15:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.