Advances and Applications in Discrete Mathematics
Volume 3, Issue 1, Pages 67 - 84
(January 2009)
|
|
GRAY CODE FOR COMPOSITIONS OF n WITH
PARTS 1 AND p
Jean-Luc Baril (France) and Céline Moreira Dos Santos (France)
|
be
the set of all n-length
binary strings such that there are at least p
consecutive
0s between two 1s. Chinburg et al. [3] give a Gray code for the set
such
that two consecutive elements differ in at most two positions which are optimal
for n
large.
In this paper, we construct a more restrictive Gray code for
in
the sense where our Gray code contains more transitions with one move than
theirs. Moreover, using a combinatorial isomorphism between the set of
n-length
binary strings and the set of n-length
permutations avoiding 123 and 132, we provide a bijection from
to
that induces a Gray code for the set
All these codes can be generated by implementing a recursive
algorithm in constant amortized time.