http://swrc.ontoware.org/ontology#TechnicalReport
Sorting by Five Prefix Reversals
en
Gunma University
Hokkaido University
Gunma University
The University of Electro-Communications
Nagoya University
Japan Advanced Institute of Science and Technology
National Institute of Informatics
Iwate University
Tetsuya Araki
Takashi Horiyama
Shin-ichi Nakano
Yoshio Okamoto
Yota Otachi
Ryuhei Uehara
Takeaki Uno
Katsuhisa Yamanaka
Various forms of sorting have been proposed. Among them, we focus on sorting by a restricted set of reversals. Namely, for a given set of pairs of indices (i.e., intervals), we want to sort an array a by successively selecting a pair i ＜ j from the set and flipping the subsequence a[i],...,a[j]. This model includes sorting by prefix reversals (a.k.a. pancake sort), sorting by adjacent transpositions, and it is an extension of the token swapping problem on a path that appears in the context of reconfiguration problems. We prove that for any natural number n, there exists a set of five intervals that can sort any sequence of length n with O(n log n) flips. Moreover, those intervals are achieved by prefixes of the indices. Such a construction with a constant number of intervals has only been known when n is odd and n mod 8 ≠ 1. The number of flips is asymptotically best possible when only a constant number of intervals are used.
Various forms of sorting have been proposed. Among them, we focus on sorting by a restricted set of reversals. Namely, for a given set of pairs of indices (i.e., intervals), we want to sort an array a by successively selecting a pair i ＜ j from the set and flipping the subsequence a[i],...,a[j]. This model includes sorting by prefix reversals (a.k.a. pancake sort), sorting by adjacent transpositions, and it is an extension of the token swapping problem on a path that appears in the context of reconfiguration problems. We prove that for any natural number n, there exists a set of five intervals that can sort any sequence of length n with O(n log n) flips. Moreover, those intervals are achieved by prefixes of the indices. Such a construction with a constant number of intervals has only been known when n is odd and n mod 8 ≠ 1. The number of flips is asymptotically best possible when only a constant number of intervals are used.
AN1009593X
研究報告アルゴリズム（AL）
2020-AL-179
1
1-7
2020-08-25
2188-8566