We introduce a sorting machine consisting of k+1 stacks in series: the first k stacks can only contain elements in decreasing order from top to bottom, while the last one has the opposite restriction. This device generalizes the DI-machine introduced by Rebecca Smith, which studies the case k=1. Here we show that, for k=2, the set of sortable permutations is a class with infinite basis, by explicitly finding an antichain of minimal nonsortable permutations. This construction can easily be adapted to each k⩾3. Next we describe an optimal sorting algorithm, again for the case k=2. We then analyze two types of left-greedy sorting procedures, obtaining complete results in one case and only some partial results in the other one. We close the paper by discussing a few open questions.
Stack sorting with increasing and decreasing stacks / Cerbai, G; Cioni, L; Ferrari, L. - In: ELECTRONIC JOURNAL OF COMBINATORICS. - ISSN 1077-8926. - ELETTRONICO. - 27:(2020), pp. 0-0. [10.37236/9154]
Stack sorting with increasing and decreasing stacks
Cerbai, G;Cioni, L;Ferrari, L
2020
Abstract
We introduce a sorting machine consisting of k+1 stacks in series: the first k stacks can only contain elements in decreasing order from top to bottom, while the last one has the opposite restriction. This device generalizes the DI-machine introduced by Rebecca Smith, which studies the case k=1. Here we show that, for k=2, the set of sortable permutations is a class with infinite basis, by explicitly finding an antichain of minimal nonsortable permutations. This construction can easily be adapted to each k⩾3. Next we describe an optimal sorting algorithm, again for the case k=2. We then analyze two types of left-greedy sorting procedures, obtaining complete results in one case and only some partial results in the other one. We close the paper by discussing a few open questions.File | Dimensione | Formato | |
---|---|---|---|
9154-PDF file-30554-2-10-20200104.pdf
accesso aperto
Descrizione: Articolo principale
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Open Access
Dimensione
197.93 kB
Formato
Adobe PDF
|
197.93 kB | Adobe PDF |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.