使用单一堆栈生成置换 [英] Generate permutation using a single stack

问题描述

任何人能请解释一下算法只使用单一堆栈和push和pop时产生的排列可能是唯一允许的操作。 搜索关于它的很多，但没有确定的答案。 还这样排列的总数由Catalan数给出。但我无法得到证明的。请解释一下，以及如果可能的话。

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.

有关这个问题的进一步的细节，并与Catalan数的关系，去找Knuth的计算机程序设计艺术，第1卷（第3版）的副本 - 它在§2.2.1讨论;见练习2 - （！和我页上图的更好的版本240）。5页242-243

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屋！