使用单个堆栈生成排列

Question

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

谢谢！！

Answer 1

该问题使用输入队列和输出队列以及堆栈。

这些操作是“将一个项目从输入队列推入堆栈”和“将一个项目从堆栈弹出到输出队列”。

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

             stack

例如，对于输入 1 2 3，您可以按照以下顺序获取输出 2 1 3：

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

但是，如果您尝试生成 3 1 2，您将遇到困难。

---

如何生成这些操作可能的所有排列？嗯，递归地做起来很简单：在任何给定的状态（其中“状态”由输入队列、堆栈和输出队列的内容组成）中，最多有两个可以执行的可能操作（您可以推送如果输入队列上至少有一项；如果堆栈上至少有一项，则可以弹出），这将为您提供最多两种可能的新状态供您探索。

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

Answer 2

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

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

2. 写入输出同样是顺序发生的，写入输出的数据一旦写入就无法读取。

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

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

Wiki：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

或者如果您修复排列，问题就会变得有限，并且您同样不需要堆栈。您只需将常用算法展开到所有输入的特殊情况（即就像在编译器中进行部分评估一样）。这是非常可怕的，所以我不会费心写出所有细节，但它仍然有效，因为可能的输入总数是一个固定的（但很大！）常量。

Answer 3

我正在考虑同样的问题，最终编写了一个小的 Prolog 程序来生成排列，并“发现”了与加泰罗尼亚数字的关系，然后找到了你的问题。所以这并不是你问题的真正答案，但这里是 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