کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871645 | 1440188 | 2018 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the average number of reversals needed to sort signed permutations
ترجمه فارسی عنوان
به طور متوسط تعداد معکوس مورد نیاز برای مرتب سازی تغییرات امضا شده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
ترکیبیات جایگزینی، مرتب سازی زیرمجموعه های امضا شده توسط معکوس، میانگین تعداد معکوس،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The recurrence formula is built based on the analysis of the probability that two nodes of the breakpoint graph belong to the same alternating cycle among all the breakpoint graphs related with permutations of length n. Through this analysis it is possible to compute the average reversal distance for signed variations of the identity permutation. Also, lower and upper bounds of the average reversal distance for signed permutations are provided. Additionally, based on computational data, it is shown how these bounds can be used in order to propose concrete upper and lower bounds.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 235, 30 January 2018, Pages 59-80
Journal: Discrete Applied Mathematics - Volume 235, 30 January 2018, Pages 59-80
نویسندگان
Thaynara Arielly de Lima, Mauricio Ayala-Rincón,