Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650300 | Discrete Mathematics | 2007 | 5 Pages |
Abstract
We consider the problem of determining the maximum number of moves required to sort a permutation of [n][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][n] can be transformed to the identity in at most ⌊2n/3⌋⌊2n/3⌋ such moves and that some permutations require at least ⌊n/2⌋⌊n/2⌋ moves.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Daniel W. Cranston, I. Hal Sudborough, Douglas B. West,