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