使用单个堆栈生成排列

Question

任何人都可以解释算法,以便在仅使用单个堆栈时生成可能的排列,并且push和pop是唯一允许的操作.已经搜索了很多,但没有明确的答案.此类排列的总数也由加泰罗尼亚数字给出.但我没有得到证据.请尽可能解释一下.

谢谢!!

Answer 1

此问题使用输入队列和输出队列以及堆栈.

操作是"将项目从输入队列推送到堆栈"和"将项目从堆栈弹出到输出队列".

                  1 2 3
output  ______   ______  input  
              \ /
        <--+   |   +---
       pop |   |   | push
           |   |   v

             stack

例如,使用输入1 2 3,您可以2 1 3按以下顺序获取输出:

• 将1从输入推送到堆栈
• 将2从输入推送到堆栈
• 弹出2从堆栈到输出
• 弹出1从堆栈到输出
• 将3从输入推送到堆栈
• 弹出3从堆栈到输出

但是如果你试图生成,你会很难3 1 2.

如何生成这些操作可能产生的所有排列？好吧,递归执行是微不足道的:在任何给定状态("状态"由输入队列,堆栈和输出队列的内容组成)中,最多可以执行两种可能的操作(可以推送)如果输入队列中至少有一个项目;如果堆栈中至少有一个项目,则可以弹出),这将最多为您提供两个可供探索的新状态.

有关此问题的进一步的细节,并与Catalan数的关系,去找Knuth的"计算机程序设计艺术",第1卷的副本 - 它在§2.2.1讨论(第3版); 请参阅第242-243页的练习2 - 5(以及第240页的更好的图表版本!).