2022-08-08T14:12:16Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:002065092020-08-24T15:00:00Z01164:02592:10084:10299
Sorting by Five Prefix ReversalsSorting by Five Prefix Reversalsenghttp://id.nii.ac.jp/1001/00206409/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=206509&item_no=1&attribute_id=1&file_no=1Copyright (c) 2020 by the Information Processing Society of JapanGunma UniversityHokkaido UniversityGunma UniversityThe University of Electro-CommunicationsNagoya UniversityJapan Advanced Institute of Science and TechnologyNational Institute of InformaticsIwate UniversityTetsuya, ArakiTakashi, HoriyamaShin-ichi, NakanoYoshio, OkamotoYota, OtachiRyuhei, UeharaTakeaki, UnoKatsuhisa, YamanakaVarious 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-1791172020-08-252188-85662020-08-20