首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号