  Given a binary word relation $\tau$ onto A * and a finite language X
$\subseteq$ A * , a $\tau$-Gray cycle over X consists in a permutation w [i]
0$\le$i$\le$|X|--1 of X such that each word w [i] is an image under $\tau$ of
the previous word w [i--1]. We define the complexity measure $\lambda$A,$\tau$
(n), equal to the largest cardinality of a language X having words of length at
most n, and st. some $\tau$-Gray cycle over X exists. The present paper is
concerned with $\tau$ = $\sigma$ k , the so-called k-character substitution,
st. (u, v) $\in$ $\sigma$ k holds if, and only if, the Hamming distance of u
and v is k. We present loopless (resp., constant amortized time) algorithms for
computing specific maximum length $\sigma$ k-Gray cycles.
