2026-07-21T12:57:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8695 2024-03-06T10:43:01Z ddc:004 open_access

Can a permutation be sorted by best short swaps? Zhang, Shu Zhu, Daming Jiang, Haitao Ma, Jingjing Guo, Jiong Feng, Haodi Algorithm Complexity Short Swap Permutation Reversal A short swap switches two elements with at most one element caught between them. Sorting permutation by short swaps asks to find a shortest short swap sequence to transform a permutation into another. A short swap can eliminate at most three inversions. It is still open for whether a permutation can be sorted by short swaps each of which can eliminate three inversions. In this paper, we present a polynomial time algorithm to solve the problem, which can decide whether a permutation can be sorted by short swaps each of which can eliminate 3 inversions in O(n) time, and if so, sort the permutation by such short swaps in O(n^2) time, where n is the number of elements in the permutation. A short swap can cause the total length of two element vectors to decrease by at most 4. We further propose an algorithm to recognize a permutation which can be sorted by short swaps each of which can cause the element vector length sum to decrease by 4 in O(n) time, and if so, sort the permutation by such short swaps in O(n^2) time. This improves upon the O(n^2) algorithm proposed by Heath and Vergara to decide whether a permutation is so called lucky. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shu Zhang and Daming Zhu and Haitao Jiang and Jingjing Ma and Jiong Guo and Haodi Feng 2018 Is Part Of LIPIcs, Volume 105, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2018.14 urn:nbn:de:0030-drops-86957 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2018.14 eng https://creativecommons.org/licenses/by/3.0/legalcode