The term restricted growth string typically refers to strings of non-negative integers \(a_1 a_2 \cdots a_n\) (with \(a_1 = 0\) ) in which the next symbol is at most one more than the maximum of the previous symbols: \(0 \le a_i \le \max (a_1 \cdots a_{i-1})+1\) for \(2 \le i \le n\) .These strings are counted by the Bell numbers \(\mathcal {B}_{n}\) (Oeis A000110) and encode set partitions. Kerr showed that the following algorithm generates a Gray code starting from  \(0^n\) : greedily maximize the rightmost possible digit that creates a new string. For example, the result is 000, 001, 011, 012, 010 for \(n=3\) ;the last transition causes the rightmost digit to decrease to 0 because that is the largest value for that digit that creates a new string. Kerr’s algorithm is a special case of more general results for \(\textbf{e}\) -restricted and \(\textsf{st}\) -restricted strings by Mansour and Vajnovszki (and Nassar), although those authors did not describe their results greedily.We show that the same greedy max-right algorithm generates restricted growth strings parameterized by \((s, f, \textbf{c})\) : \(0 \le a_1 \le s{-}1\) and \(0 \le a_i \le f(a_1 a_2 \cdots a_{i-1}) + c_i\) where f is any function with \(f \ge 0\) and \(c_i \ge 1\) are constants for each digit.The resulting Gray codes change a single digit by \(-1\) or \(-2\) (cyclically).Special cases include the binary reflected Gray code ( \(s = 2\) , \(f = 0\) , \(\textbf{c} = 1^n\) ) and the aforementioned results.We also consider restricted growth string counted by the k-Catalan numbers and provide loopless algorithms for generating these k-Catalan strings and Bell strings.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Maximize the Rightmost Digit:Gray Codes for Restricted Growth Strings

  • Yuan Qiu,
  • Joe Sawada,
  • Aaron Williams

摘要

The term restricted growth string typically refers to strings of non-negative integers \(a_1 a_2 \cdots a_n\) (with \(a_1 = 0\) ) in which the next symbol is at most one more than the maximum of the previous symbols: \(0 \le a_i \le \max (a_1 \cdots a_{i-1})+1\) for \(2 \le i \le n\) .These strings are counted by the Bell numbers \(\mathcal {B}_{n}\) (Oeis A000110) and encode set partitions. Kerr showed that the following algorithm generates a Gray code starting from  \(0^n\) : greedily maximize the rightmost possible digit that creates a new string. For example, the result is 000, 001, 011, 012, 010 for \(n=3\) ;the last transition causes the rightmost digit to decrease to 0 because that is the largest value for that digit that creates a new string. Kerr’s algorithm is a special case of more general results for \(\textbf{e}\) -restricted and \(\textsf{st}\) -restricted strings by Mansour and Vajnovszki (and Nassar), although those authors did not describe their results greedily.We show that the same greedy max-right algorithm generates restricted growth strings parameterized by \((s, f, \textbf{c})\) : \(0 \le a_1 \le s{-}1\) and \(0 \le a_i \le f(a_1 a_2 \cdots a_{i-1}) + c_i\) where f is any function with \(f \ge 0\) and \(c_i \ge 1\) are constants for each digit.The resulting Gray codes change a single digit by \(-1\) or \(-2\) (cyclically).Special cases include the binary reflected Gray code ( \(s = 2\) , \(f = 0\) , \(\textbf{c} = 1^n\) ) and the aforementioned results.We also consider restricted growth string counted by the k-Catalan numbers and provide loopless algorithms for generating these k-Catalan strings and Bell strings.