Efficient generation of restricted growth words

详细信息    查看全文

• 作者：Toufik Mansour ; Vincent Vajnovszki
• 关键词：Algorithms ; Restricted growth functions/words ; Gray codes
• 刊名：Information Processing Letters
• 出版年：2013
• 出版时间：30 August, 2013
• 年：2013
• 卷：113
• 期：17
• 页码：613-616
• 全文大小：193 K

文摘

A length n restricted growth word is a word over the set of integers where and each , , lies between 0 and the value of a word statistics of the prefix 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.