کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419204 | 683753 | 2016 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Greedy flipping of pancakes and burnt pancakes
ترجمه فارسی عنوان
پر زرق و برق پر از پانکک و پنکیک سوز
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم حریص، کد خاکستری تغییرات جایگزینی امضا شده، پیشوند-معکوس گروه متقارن، گروه متقارن امضا شده، گراف کیلی، چرخه همیلتون
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We prove that a stack of nn pancakes is rearranged in all n!n! ways by repeatedly applying the following rule: Flip the maximum number of pancakes that gives a new stack. This complements the previously known pancake flipping Gray code (Zaks, 1984) which we also describe as a greedy algorithm: Flip the minimum number of pancakes that gives a new stack . Surprisingly, these maximum and minimum flip algorithms also rearrange stacks of nn ‘burnt’ pancakes in all 2nn!2nn! ways. We conjecture that these four algorithms are essentially the only greedy algorithms for rearranging pancakes and burnt pancakes in all possible ways using flips.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 210, 10 September 2016, Pages 61–74
Journal: Discrete Applied Mathematics - Volume 210, 10 September 2016, Pages 61–74
نویسندگان
Joe Sawada, Aaron Williams,