# Generating \(m\)-[PERSON] Gray Codes and Related Algorithms
## 3 The \(m\)-Ary Modular (Shifted) Gray Code
Recursive algorithms are more compact, but in most cases recursion slows down the execution. Some of the algorithms are very convenient for generating part of the codewords, which allows breaking the code into parts that are generated separately, but with less efficiency. We have also considered in detail the issue of generating a maximum set of non-proportional vectors in \(\mathbb{Z}_{m}^{n}\) in a Gray code, which is important in coding theory. Comparing the algorithms, we can say that those for the modular Gray code are simpler (and some of them faster) than the corresponding algorithms for the reflected Gray code. However, the corresponding algorithms have time complexity of the same type as follows:

* The nested loop Algorithms 3 and 10, the examples for \(n=4\), have time complexity \(\Theta(m^{4})\). In the general case, for \(n\) nested loops, they have a time complexity of the type \(\Theta(m^{n})\). * The non-recursive algorithms: 5, 12, 8 and 13 to generate all or part of all codewords, are CAT-algorithms. Also the stack Algorithms 6 and 15 are loopless algorithms, i.e., the number of operations to obtain the next codeword is constant and does not depend on \(n\) and \(m\). * All ranking and unranking Algorithms 7 and 9 have time complexity \(\Theta(n)\). We also want to pay special attention to another of our motivations for this paper, namely to generate interest in research on non-binary Gray codes. While binary Gray codes have an enormous research interest, e.g., defining equivalences, relating graphs and other combinatorial configurations [14], for non-binary Gray codes there are only a few papers on their generation. Conceptualization, I.B. and V.B. ; methodology, I.B. and V.B. ; software, I.B. and V.B. ; validation, I.B., V.B. and M.P.-G.; formal analysis, S.B. and V.B. ; investigation, I.B. and V.B. ; writing--original draft preparation, S.B. and V.B. ; writing--review and editing, S.B. and M.P.-G. visualization, I.B. ; supervision, S.B. and I.B. ; funding acquisition, S.B., I.B., V.B. and M.P.-G. All authors have read and agreed to the published version of the manuscript. This research was partially supported by Bulgarian National Science Fund grant number KP-06-H62/2/13.12.2022. No new data were created or analyzed in this study. Data sharing is not applicable to this article. The authors declare no conflicts of interest. ## References

* (1) [PERSON] Pulse Code Communication. U.S. Patent 2,632,058, 17 March 1953. * (2) [PERSON] _The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1;_ Addison-Wesley: Boston, MA, USA, 2014. * (3) [PERSON]; [PERSON] On \(m\)-ary Gray codes. _Inf. Sci._**1978**, _15_, 31-43. [CrossRef]
* (4) [PERSON] On Generating the N-ary Reflected Gray Codes. _IEEE Trans. Comput._**1984**, _c-33_, 739-741. * (5) [PERSON]; [PERSON]; [PERSON] Q-ary Gray codes and weight distributions. _Appl. Math. Comput._**1999**, _103_, 97-109. [CrossRef]
* (6) [PERSON] A Survey of Combinatorial Gray Codes. _Siam Rev._**1997**, _39_, 605-629. [CrossRef]
* (7) [PERSON] Combinatorial Generation. Working Version (1)-CSC 425/520). In _Preliminary Working Draft_; University of Victoria: Victoria, BC, Canada, 2003. * (8) [PERSON] Combinatorial Gray Codes--An Updated Survey. _Electron. J. Comb._**2023**, _DS26_. [CrossRef] [PubMed]
* (9) [PERSON] Bounds, Constructions and Classification of Optimal Codes. Ph.D. Dissertation, Technical University, Gabrovo, Bulgaria, 2004. (In Bulgarian)
* (10) [PERSON] Generalized Gray Codes with Applications. _Proc. Natl. Sci. Counc. ROC(A)_**1998**, _22_, 841-848. * [PERSON] et al. (1976) [PERSON]; [PERSON]; [PERSON] Efficient generation of the binary reflected gray code and its applications. _Commun. ACM_**1976**, 19, 517-521. [CrossRef]
* [PERSON] and [PERSON] (1999) [PERSON]; [PERSON] _Combinatorial Algorithms: Generation, Enumeration and Search_; CRC Press: Cambridge, MA, USA, 1999.