限制堆栈的堆栈排序

原文题目：Stack sorting with restricted stacks

摘要：描述和枚举排列的(经典)问题，可以使用串联连接的两个堆栈进行排序，这个问题在很大程度上仍然是开放的。在本文中，我们讨论了一个相关的问题，在这个问题中，我们对程序和堆栈都施加了限制。更准确地说，我们考虑了一个贪婪的算法，其中我们执行最右边的合法操作(这里“最右边”指的是通常的堆栈排序问题的表示)。此外，第一个堆栈必须是σ-避免，为了某种排列σ，这意味着，在每一步中，堆栈中维护的元素都避免使用模式。σ自上而下阅读时。因为这组排列可以按照这样的设备排序(我们称之为σ-机器)并不总是一个类，当它发生时，了解它是很有趣的。我们将证明σ-相关可排序排列不是类的机器按加泰罗尼亚数计算。此外，我们还将分析两个具体的σ-机器的全部细节(即σ=321和σ=123)，为它们中的每一个提供可排序排列的完整特征和枚举。

原文作者：Giulio Cerbai, Anders Claesson, Luca Ferrari

原文地址：https://arxiv.org/abs/1907.08142