Generating <i>m</i>-Ary Gray Codes and Related Algorithms

Abstract

In this work, we systematize several implementations of the Gray code over an alphabet with m≥2 elements, which we present in C code so that they can be used directly after copying from the text. We consider two variants—reflected and modular (or shifted) m-ary Gray codes. For both variants, we present the ranking and unranking functions, as well as algorithms for generating only a part of the code, more precisely the codewords between two given vectors. Finally, we give algorithms that generate a maximal set of non-proportional vectors of length n over the given alphabet in a Gray code.

Keywords

• Gray code
• <i>m</i>-ary Gray code
• combinatorial algorithms
• combinatorial generation
• ranking
• unranking