On Lexicographic and Colexicographic Orders and the Mirror (Left-Recursive) Reflected Gray Code for m-ary Vectors

In this paper, we investigate the lexicographic and colexicographic orderings of m-ary vectors of length n, as well as the mirror (left-recursive) reflected Gray code, complementing the classical m-ary reflected Gray code. We present efficient algorithms for generating vectors in each of these orders, each achieving constant amortized time per vector. Additionally, we propose algorithms implementing the four fundamental functions in generating combinatorial objects—successor, predecessor, rank, and unrank—each with time complexity Θ(n). The properties and the relationships between these orderings and the set of integers {0,1,…,mn−1} are examined in detail. We define explicit transformations between the different orders and illustrate them as a digraph very close to the complete symmetric digraph. In this way, we provide a unified framework for understanding ranking, unranking, and order conversion. Our approach, based on emulating the execution of nested loops, proves to be powerful and flexible, leading to elegant and efficient algorithms that can be extended to other combinatorial generation problems. The mirror m-ary Gray code introduced here has potential applications in coding theory and related areas. By providing an alternative perspective on m-ary Gray codes, we aim to inspire further research and applications in combinatorial generation and coding.