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 linear time complexity. 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 K↔5. 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 powerful and flexible, leading to elegant and efficient algorithms that can be extended to the generation of submultisets, the generation of numbers in mixed-radix number systems, and related problems. The mirror m-ary Gray code introduced here has potential applications in coding theory and related areas.