Short proofs for cut-and-paste sorting of permutations |
| |
Authors: | Daniel W. Cranston |
| |
Affiliation: | a University of Illinois, USA b University of Texas, Dallas, USA |
| |
Abstract: | We consider the problem of determining the maximum number of moves required to sort a permutation of [n] using cut-and-paste operations, in which a segment is cut out and then pasted into the remaining string, possibly reversed. We give short proofs that every permutation of [n] can be transformed to the identity in at most ⌊2n/3⌋ such moves and that some permutations require at least ⌊n/2⌋ moves. |
| |
Keywords: | Sorting Permutation Reversal Transposition Cut-and-paste |
本文献已被 ScienceDirect 等数据库收录! |
|