使用单个堆栈生成排列 [英] Generate permutation using a single stack

问题描述

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

Can anyone please explain algorithm to generate the permutations possible when using only a single stack and push and pop are the only operations allowed. Have searched about it a lot, but no definite answer. Also the total number of such permutations is given by catalan numbers. But I fail to get a proof for that. Kindly explain that as well if possible.

谢谢！！

推荐答案

这个问题使用了一个输入队列和一个输出队列以及一个栈.

This problem uses an input queue and an output queue as well as a stack.

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

The operations are "push an item from the input queue onto the stack" and "pop an item from the stack onto the output queue".

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

             stack

例如，输入1 2 3，可以得到输出2 1 3，顺序如下:

For example, with the input 1 2 3, you can get the output 2 1 3 with the following sequence:

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

但如果你尝试生成 3 1 2，你会遇到困难.

But you'll have a hard time if you try to generate 3 1 2.

如何通过这些操作生成所有可能的排列?好吧，递归执行很简单:在任何给定状态(状态"由输入队列、堆栈和输出队列的内容组成)，您最多可以执行两种可能的操作(您可以推送如果输入队列中至少有一项；如果堆栈上至少有一项，则可以弹出)，这将为您提供最多两种可能的新状态供您探索.

How do you generate all the permutations that are possible with these operations? Well, it's trivial to do recursively: in any given state (where the "state" consists of the contents of the input queue, the stack, and the output queue), there are at most two possible operations you can perform (you can push if there is at least one item on the input queue; you can pop if there is at least one item on the stack), which will give you at most two possible new states to explore.

有关此问题的更多详细信息以及与加泰罗尼亚数字的关系，请查找 Knuth 的计算机编程艺术"第 1 卷(第 3 版)的副本 - 在第 2.2.1 节中进行了讨论；请参阅第 242-243 页上的练习 2 - 5(以及第 240 页上我的图表的更好版本！).

For further detail regarding this problem, and the relationship with Catalan numbers, go and find a copy of Knuth's "The Art of Computer Programming", volume 1 (3rd ed.) - it's discussed in §2.2.1; see exercises 2 - 5 on pp. 242-243 (and a better version of my diagram on p. 240!).

这篇关于使用单个堆栈生成排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！