کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650300 | 1342483 | 2007 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Short proofs for cut-and-paste sorting of permutations
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issue 22, 28 October 2007, Pages 2866–2870
Journal: Discrete Mathematics - Volume 307, Issue 22, 28 October 2007, Pages 2866–2870
نویسندگان
Daniel W. Cranston, I. Hal Sudborough, Douglas B. West,