7
$\begingroup$

Suppose given $k\geq 2$ stacks $S_1,S_2,\dots,S_k$, and we have $n$ numbers that we can push a number to $S_1$ and pop and push it into $S_2$ and finally we can pop from $S_k$. How many permutations can generated by this method of using $k$ stacks?

Also I read this post but i can't figured out how many stacks we need to generate $n!$ permutation or how many permutation generated by using $k$ stacks?

$\endgroup$
3
  • $\begingroup$ It smells like induction. Not an easy problem! $\endgroup$
    – String
    Nov 19, 2021 at 8:05
  • $\begingroup$ I think the first stack and the output make the problem a bit unclear. It is easier for me to think of the first stack as an ordered input stream and so the output should be a permutated output of the process. Then the number of stacks serving a purpose will be one less. $\endgroup$
    – String
    Nov 19, 2021 at 8:12
  • $\begingroup$ And the output stream simply pops from the last stack at strategic points in the process. $\endgroup$
    – String
    Nov 19, 2021 at 8:13

1 Answer 1

1
$\begingroup$

DISCLAIMER: This is not (by far) a complete solution, only some thoughts and partial analysis!

Here is my initial model of the problem. I wrote a backtracking algorithm in C# which can be summarized as:

Function BacktrackingAlgorithm(system of stacks)
{
  for each non-empty stack:
  {
    Perform: pop(i) -> push(i + 1) // i + 1 = k is output stack
    BacktrackingAlgorithm(system of stacks) // recursive
    Revert: pop(i + 1) -> push(i)
  }

  if (all stacks are empty) record stats for permutation
}

Now my stacks are $0$-indexed $S_0,...,S_{k-1}$ and $S_0=[1,2,...,n]$ is loaded with $n$ on top. Then for $(n,k)=(3,2)$ I got the following output, where x>y>z denotes the sequence of stacks to pop from.

0>0>0>1>1>1 gives 1 2 3
0>0>1>0>1>1 gives 2 1 3
0>0>1>1>0>1 gives 2 3 1
0>1>0>0>1>1 gives 3 1 2
0>1>0>1>0>1 gives 3 2 1

Which is $5$ of the desired $3!=6$ permutations (missing 1 3 2). But when I set $(n,k)=(4,2)$ I only get $14$ of $24$ permutations whereas $(n,k)=(4,3)$ produces all $4!=24$ BUT of course has multiple ways of producing many of them. This leads me to the obvious question:

Number of valid pop-sequences?

Each number $1,...,n$ must be popped once from every stack to reach the output. Hence stack $i$ has had $n$ pop-operations. A total of $n\cdot k$ pops in total. How many pop-sequences x>y>z>... can we form for the case $(n,k)$ based on this? An upper bound is: $$ \operatorname{popsequences}(n,k)\leq\binom {nk}n\cdot\binom{n(k-1)}{n}\cdots\binom {n\cdot2}n $$ so for the case $(n,k)=(4,3)$ we must have: $$ \operatorname{popsequences}(4,3)\leq\binom {12}4\cdot\binom{8}{4}=34650 $$ My program tells me the actual figure is $462$ valid pop-sequences. This is because it is not valid to pop from the last stack to begin with for instance. A stack need to contain an element before one can start popping. So many sequences in the upper bound are invalid. And the number does not resemble a value directly related to the $n!$ permutations we want to produce. This is quite a messy problem!

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .