6533b7d2fe1ef96bd125e2ae

RESEARCH PRODUCT

Efficient generation of restricted growth words

Vincent VajnovszkiToufik Mansour

subject

010102 general mathematicsBinary numberValue (computer science)0102 computer and information sciences[ MATH.MATH-CO ] Mathematics [math]/Combinatorics [math.CO]01 natural sciencesComputer Science ApplicationsTheoretical Computer SciencePrefixCombinatoricsGray code010201 computation theory & mathematics[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]Signal ProcessingPartial word0101 mathematicsConstant (mathematics)ComputingMilieux_MISCELLANEOUSWord (group theory)Information SystemsMathematics

description

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

yearjournalcountryeditionlanguage
2013-08-01Information Processing Letters
https://doi.org/10.1016/j.ipl.2013.05.008