کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428946 686973 2013 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Efficient generation of restricted growth words
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Efficient generation of restricted growth words
چکیده انگلیسی


• Restricted growth words simultaneously generalize restricted growth functions, staircase words and ascent sequences.
• They are defined using statistics on words.
• We give a recursive constant average time algorithm for generating, in Gray code order, restricted growth words.

A length n   restricted growth word is a word w=w1w2…wnw=w1w2…wn over the set of integers where w1=0w1=0 and each wiwi, i>1i>1, lies between 0 and the value of a word statistics of the prefix w1w2…wi−1w1w2…wi−1 of w, plus one. Restricted growth words simultaneously generalize combinatorial objects as restricted growth functions, staircase words and ascent or binary sequences. Here we give a generic generating algorithm for restricted growth words. It produces a Gray code and runs in constant average time provided that the corresponding statistics has some local properties.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 113, Issue 17, 30 August 2013, Pages 613–616
نویسندگان
, ,