Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Rearranging Two Dimensional Arrays by Prefix Reversals
verfasst von : Akihiro Yamamura
Erschienen in: Reachability Problems
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Generalizing the pancake sorting problem, we consider a reachability problem which asks whether an arbitrary two dimensional array can be obtained from an initial array by prefix reversals. In the case of the pancake sorting problem, sorting is always possible, whereas, it is not clear whether a rearrangement of two dimensional arrays is always possible. We shall prove any array is reachable from the initial array by prefix reversals unless the numbers of both rows and columns are divisible by 4. Using group theory, we also give a necessary and sufficient condition that an array is reachable from the initial array in such a case. We also give upper bounds on the number of prefix reversals to rearrange.