使用单个栈生成排列

Question

请问有人能够解释一下使用单个栈且只允许push和pop操作时，如何生成可能的排列算法？我已经搜索了很多，但没有明确的答案。此外，这样排列的总数由卡特兰数给出。但我无法证明这一点。如果可能的话，请详细解释。

谢谢！

- Rohit Jain

---

我不理解“单栈”要求。如果我使用一个额外的数据结构，它不是“栈”，而是“数组”、“队列”或“列表”，那怎么办？那样可以吗？我猜想这是不允许的。但在这种情况下，我不明白如何可能。为了检索堆栈中深度为n的元素，您必须弹出并存储在某个地方堆栈顶部的n个元素，从而创建了额外的O(n)内存需求。我有什么遗漏吗？ - AnT stands with Russia

此外，可能可以使用语言级递归来实现它，这意味着第二个堆栈将隐式地作为嵌套函数调用的本地上下文的“堆栈”存在。这是允许的吗？ - AnT stands with Russia

我的猜测是这是一些奇怪的递归作业？编辑哈哈，Audrey，在我做同样的事情时你把它打了出来。 - Perception

排列应该如何表示？它在运行时固定还是动态指定？输出应该如何处理？它是逐个放入只读输出队列中，还是仅存储在堆栈中？此外，输入如何指定？它是否再次预加载到堆栈中？允许使用多少临时存储器？ - Mikola

我所说的单栈是指只允许push和pop操作。输入以队列的形式给出，如1 2 3 4 5，一旦元素被弹出，它就会被发送到输出队列，并且不能再次push回去。 - Rohit Jain

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卷（第3版）的副本-它在第2.2.1节中讨论；请参见第242-243页上的练习2-5（以及页面240上更好的版本的图表！）。

- Matthew Slattery

Answer 2

首先，在以下假设下，不可能编写一个算法来对任意排列进行操作：

1. 只能按顺序从输入中读取。

2. 同样地，写入输出是按顺序进行的，并且一旦写入，就无法再读取写入到输出的数据。

3. 除了一个栈外，您只允许使用恒定数量的内存。（这意味着不能使用额外的递归或数据结构）。

这是上下文无关语言泵引理的一种结果：

维基百科：http://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages

（或者也可以查看：Michael Sipser（1997年）。计算理论介绍。我相信这是第4章中的一个练习题。）

现在，您可以通过破坏其中任何一个假设来轻松实施解决此问题的算法。例如，如果您可以任意读取输入，则不需要使用堆栈：

def permute(seq, permutation):
    result = []
    for i in permutation:
        result.push(seq[i])
    return result

如果你固定一个排列，问题就变得有限了，你同样不需要使用栈。你只需展开通常的算法以覆盖所有输入的特殊情况（就像编译器中进行部分求值一样）。这相当麻烦，所以我不会费力写出所有细节，但这仍然有效，因为可能输入的总数是一个固定的（但很大！）常数。

- Mikola

Answer 3

我曾经思考过同样的问题，最终编写了一个小的Prolog程序来生成排列组合，并“发现”了与Catalan数的关系，然后找到了你的问题。所以这并不是真正回答你的问题，但这是Prolog程序：

% Generate permutation counts
count_pushpop(N-K) :-
    length(_, N),
    findall(Seq, pushpop(N, Seq), Seqs),
    length(Seqs, K).


% Create an integer sequence from 1 to N
% and permutate it using all possible push-pop
% operations starting with an empty stack.
pushpop(N, Seq) :-
    numlist(1, N, List),
    pushpop(List, [], Seq).


% Generate all the possible ways a list
% of items can be pushed into a stack
% and poped out of it.
pushpop([], [], []).

pushpop([H | List], Stack, Seq) :-
    pushpop(List, [H | Stack], Seq).

pushpop(List, [H | Stack], [H | Seq]) :-
    pushpop(List, Stack, Seq).

证明不是所有的 n! 种排列都是可能的：

?- findall(Seq, pushpop(3, Seq), Seqs).
Seqs = [[3, 2, 1], [2, 3, 1], [2, 1, 3], [1, 3, 2], [1, 2, 3]].

证明它生成卡特兰数（如果没有堆栈溢出，这将是一个证明；）：

?- count_pushpop(N-K).
N = K, K = 0 ;
N = K, K = 1 ;
N = K, K = 2 ;
N = 3,
K = 5 ;
N = 4,
K = 14 ;
N = 5,
K = 42 ;
N = 6,
K = 132 ;
N = 7,
K = 429 ;
N = 8,
K = 1430 ;
N = 9,
K = 4862 ;
N = 10,
K = 16796 ;
N = 11,
K = 58786 ;
N = 12,
K = 208012 ;
ERROR: Out of global stack

- Kaarel