6

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

谢谢！！

4

3 回答 3

5

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

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

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

             stack

例如，使用 input 1 2 3，您可以获得2 1 3以下序列的输出：

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

但是，如果您尝试生成3 1 2.

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

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

于 2011-06-25T23:54:09.010 回答
0

我正在考虑同样的问题，最后编写了一个小的 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
于 2013-02-11T15:44:03.833 回答
0

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

  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

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

于 2011-06-26T02:24:40.470 回答