Restricted stacks as functions
Restricted stacks as functions
复制标题
限制堆栈作为函数
DOI：
10.1016/j.disc.2021.112571
复制
发表时间：
2022
影响因子：
0.8
通讯作者：
Berlow, Katalin
中科院分区：
文献类型：
--
作者：
Berlow, Katalin
堆栈排序算法多年来一直是广泛研究的主题。在本文中，我们探讨了这个算法的一个广义版本，而不是避免一个单一的减少，堆栈避免了一组T的排列。我们用T表示这个映射。我们分类对于哪些集合T，映射s T是双射的。这个推论回答了Baril、Cerbai、Khalil和Vajnovszki关于由s {σ，τ}组成的栈排序的问题，称为（σ，τ）-机。这完全分类了在（σ，τ）-机器下的恒等式的原像σ和τ是由卡塔兰数计数的。我们还证明了置换的原像的数目在映射s T下是有界的Catalan数，与一个移动的指标。对于大小为1的T，当这个界是尖锐的时，我们准确地分类。我们还探讨了周期点和最大数目的各种s T的原像的T含有两个长度为3的排列。
The stack sort algorithm has been the subject of extensive study over the years. In this paper we explore a generalized version of this algorithm where instead of avoiding a single decrease, the stack avoids a set T of permutations. We let s T denote this map. We classify for which sets T the map s T is bijective. A corollary to this answers a question of Baril, Cerbai, Khalil, and Vajnovszki about stack sort composed with s {σ, τ}, known as the (σ, τ)-machine. This fully classifies for which σ and τ the preimage of the identity under the (σ, τ)-machine is counted by the Catalan numbers. We also prove that the number of preimages of a permutation under the map s T is bounded by the Catalan numbers, with a shift of indices. For T of size 1, we classify exactly when this bound is sharp. We also explore the periodic points and maximum number of preimages of various s T for T containing two length 3 permutations.
登录
查看更多内容
已排序和/或可排序排列
影响因子：
0.8
作者：
M. Bousquet
通讯作者：
M. Bousquet
模式类的排序和原像
DOI：
--
发表时间：
2012
期刊：
arXiv.org
影响因子：
--
作者：
Anders Claesson;Henning Úlfarsson
通讯作者：
Henning Úlfarsson
使用模式避免机对凯莱排列进行排序
DOI：
--
发表时间：
2020
期刊：
影响因子：
--
作者：
Giulio Cerbai
通讯作者：
Giulio Cerbai
剧团、累积量和堆栈排序
影响因子：
1.7
作者：
Colin Defant
通讯作者：
Colin Defant
堆栈排序图的生育率单调性和平均复杂度
DOI：
--
发表时间：
2020
期刊：
European journal of combinatorics (Print)
影响因子：
--
作者：
Colin Defant
通讯作者：
Colin Defant