Generating m-Ary Gray Codes and Related Algorithms

Abstract

In this work, we systematize several implementations of the Gray code over an alphabet with $m\ge 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.

1. Introduction

The classical version of a Gray code is an ordering of the $2^n$ binary vectors of length n such that each pair of adjacent vectors differ in a single position [1,2]. If the last and the first vectors also differ in one position, the code is said to be cyclic. Gray codes are widely used in digital communications, effective generation of combinatorial objects, etc. In coding theory, Gray codes are used for the effective generation of the codewords of a given code in order to compute some of its parameters as weight enumerator and minimum distance. To study linear codes over fields with more than two elements, we need an m-ary version of the Gray code [3,4,5]. Let ${\mathbb{Z}}_m=\{0,1,\dots ,m-1\}$ be the ring of integers modulo m, where $m>1$ is an integer, and ${\mathbb{Z}}_m^n$ be the set of all n-tuples (vectors) with coordinates from ${\mathbb{Z}}_m$. If we define addition and multiplication by a coefficient as follows

$$a+b=(a_1+b_1,\dots ,a_n+b_n),\alpha a=(\alpha a_1,\dots ,\alpha a_n)$$

for all $a=(a_1,\dots ,a_n)$, $b=(b_1,\dots ,b_n)\in {\mathbb{Z}}_m^n$ and all $\alpha \in {\mathbb{Z}}_m$, we can consider ${\mathbb{Z}}_m^n$ as a module over ${\mathbb{Z}}_m$. If m is prime, then ${\mathbb{Z}}_m$ is a prime field and ${\mathbb{Z}}_m^n$ is a vector space over this field.

Our motivation to study m-ary Gray codes in detail and develop algorithms for their generation is to use them in software to compute some important parameters and characteristics of linear codes over fields (and also over rings) with m elements. We can use already published algorithms, but our idea is to develop algorithms that are suitable for parallelization. The main reason for this is the development of computer technology in the direction of more processors, cores and threads.

A linear q-ary code $C_n$ of length n is a linear subspace of the vector space ${\mathbb{F}}_q^n$, where ${\mathbb{F}}_q$ is a finite field with q elements. If q is prime, then we can take ${\mathbb{F}}_q={\mathbb{Z}}_q$. If $q=p^s$ is a prime power with $s>1$, there is no natural ordering of the elements, so we need to define an ordering if we want to use a Gray code to generate the codewords in $C_n$. One possibility is to consider the lexicographic ordering of the field elements in a polynomial representation. Another one is to consider the elements in multiplicative form, namely

$${\mathbb{F}}_q=\{0,1,\alpha ,{\alpha }^2,\dots ,{\alpha }^{q-2}\},$$

where $\alpha \in {\mathbb{F}}_q$ is a primitive element of the field. Then, we can order the elements of the field using the bijection $\phi :{\mathbb{F}}_q\to {\mathbb{Z}}_q$ defined by $\phi \left(0\right)=0$,

$$\phi \left({\alpha }^s\right)=s\mathrm{if}s=1,\dots ,q-2,q-1.$$

All possible orderings of the elements are $q!$ and the researchers can choose the one they think is most suitable for their investigations.

Some authors consider a more general version of Gray codes, namely Combinatorial Gray Codes, which are lists of combinatorial objects in which successive objects are “close” in some sense [6,7,8]. These lists have many applications and also lead to interesting questions and results of a mathematical nature. The formal definition is the following. Let S be a finite set of combinatorial objects and R a relation on S, which we call the closeness relation. Then, a Combinatorial Gray Code for S is a listing $s_1,s_2,\dots ,s_N$ of the elements of S, where $\left|S\right|=N$, such that $(s_i,s_{i+1})\in R$ for $i=1,2,\dots ,N-1$. Sometimes, we also insist that $(s_N,s_0)\in R$; in this case, the code is said to be cyclic.

There is a graph $G=G(S,R)$, in which the closeness graph, that is naturally associated with a combinatorial Gray code. The vertices of this graph are the objects of S and edges connect those objects that are “close”; in other words, $G(S,R)$ is just the digraph of the relation R. In most instances, the closeness relation is symmetric and so G may be regarded as an undirected graph. The question of finding a Combinatorial Gray Code for S with respect to R becomes one of finding a Hamiltonian path (or cycle) in G. Conversely, a Hamiltonian path in G can be viewed as a Gray code for S.

The most popular Gray code is the binary Gray code, where S is the set of all bit-strings of fixed length and R is the relation of Hamming distance one. In this case, G is the hypercube. For the m-ary Gray codes, $S={\mathbb{Z}}_m^n$, and R is the same relation of Hamming distance one but combined with a difference in the changed position with $+1$ or $-1$.

Among the non-binary Gray codes, the most popular (and studied) are reflected and modular Gray codes [2]. Both codes are natural generalizations of the binary reflected Gray code, where the m-ary vectors are ordered such that every two consecutive vectors differ by exactly one coordinate [4,5,9]. Moreover, in an m-ary reflected Gray code, this difference is only $+1$ or $-1$, and in an m-ary modular Gray code, it is $+1$ modulo m. So, we have the minimum possible change between two consecutive vectors (codewords).

For both versions of the m-ary Gray code, we present algorithms:

• Generation in recursive and non-recursive versions;
• Ranking and unranking;
• Generation only a part of the code, namely the part between given vectors a and b, where $a,b\in {\mathbb{Z}}_m^n$.

We summarize the most popular known algorithms and also introduce some new algorithms for m-ary Gray codes. Our versions of these algorithms are presented in C code so that they can be used directly by simply copying from the text. We present several algorithms for generation of the reflected m-ary Gray code in Section 2. Section 3 is devoted to the modular (shifted) m-ary Gray code. In this case, we have also included algorithms for generating a maximal set of non-proportional vectors in ${\mathbb{Z}}_m^n$ ordered in Gray code.

2. The $\mathit{m}$-Ary Reflected Gray Code

Both m-ary Gray codes we study are generalizations of the binary reflected Gray code, but for the m-ary reflected Gray code, we have a similar recursive construction. So, we start with the properties and algorithms for this code.

We denote by $G_m\left(n\right)$ the sequence of vectors of ${\mathbb{Z}}_m^n$ in an m-ary reflected Gray code of length n. We define the code recursively, and for convenience, we associate the sequence with a matrix whose i-th row is the i-th vector in the sequence.

Definition 1.

$G_m\left(1\right)={(0,1,\dots ,m-1)}^T,$

$$G_m\left(k\right)=\left(\begin{array}{cc}0& \\ ⋮& G_m(k-1)\\ 0& \\ 1& \\ ⋮& G_m^{\ast }(k-1)\\ 1& \\ 2& \\ ⋮& G_m(k-1)\\ 2& \\ ⋮& ⋮\\ m-1& \\ ⋮& X\\ m-1& \end{array}\right)fork>1,$$

(1)

where $X=G_m(k-1)$ if m is odd, and $X=G_m^{\ast }(k-1)$ if m is is even.

By $A^{\ast }$, we denote the mirror image (reflection) of the rows of the $p\times q$ matrix $A={(a_1,a_2,\dots ,a_p)}^T$, i.e., $A^{\ast }={(a_p,\dots ,a_2,a_1)}^T$. The reflected m-ary Gray code of length n is the list of the rows of the matrix $G_m\left(n\right)$.

As given in the definition, the elements in the first column in the matrix $G_m\left(k\right)$ increase. For the other columns, we have ascending and descending order of the elements. The following theorem, similar to Theorem 2 in [4], gives information about whether a given coordinate of a given codeword is in an ascending or descending subsequence in the corresponding column.

Theorem 1.

Let $v=(v_1,v_2,\dots ,v_n)$ be a codeword of the m-ary reflected Gray code $G_m\left(n\right)$ for $m\ge 2$ and $n\ge 2$. When $S_i={\sum }_{j=1}^{i-1}{v}_j$ is even, then $v_i$, and for $1<i\le n$, is in a subsequence of digits in ascending order; otherwise, it is in a subsequence of digits in descending order.

Proof. 

We will use the following observation that follows directly from the definition and is more visible, if we look at the matrix $G_m\left(k\right)$. The first coordinate $v_1$ is always in a sequence in ascending order. For any coordinate position i, $v_i$ can be considered as an element in the first column in one of the matrices $G_m(n-i+1)$ or $G_m^{\ast }(n-i+1)$ (according to the recursive structure of the matrices in (1)). Moreover, if $v_i$ is in the first column in a matrix $G_m(n-i+1)$, then it is in a subsequence of digits in ascending order, but if $v_i$ is in the first column in a matrix $G_m^{\ast }(n-i+1)$, it is in a subsequence of digits in descending order.

We will prove this theorem by induction. According to (1), if $v_1$ is even then $v_2$ is in the first column of $G_m(n-1)$; otherwise, $v_2$ is in the first column of $G_m^{\ast }(n-1)$. Therefore, $v_2$ is in a subsequence of digits in ascending order when $v_1$ is even, and in descending order if $v_1$ is odd.

Suppose that the statement holds for $i=k<n$ and consider the next coordinate $v_{k+1}$. Now, we consider the following cases:

• Let $S_k$ be even. According to the induction hypothesis, $v_k$ is in a subsequence of digits in ascending order and can be considered as an element in the first column in a corresponding matrix $G_m(n-k+1)$. Then, according to the base step, $v_{k+1}$ is in a subsequence of digits in ascending order when $v_k$ is even, and in descending order if $v_k$ is odd. Since $S_{k+1}=S_k+v_k\equiv v_k(mod2)$ in this case, $v_{k+1}$ is in a subsequence of digits in ascending order when $S_{k+1}$ is even, and in descending order if $S_{k+1}$ is odd.
• Let $S_k$ be odd. Then, $v_k$ is in a subsequence of digits in descending order and can be considered as an element in the first column in a matrix $G_m^{\ast }(n-k+1)$. Therefore, we have the reverse situation of the previous case, namely $v_{k+1}$ is in a subsequence of digits in descending order when $v_k$ is even, and in ascending order if $v_k$ is odd. Now, $S_{k+1}=S_k+v_k\equiv v_k+1(mod2)$, and so again $v_{k+1}$ is in a subsequence of digits in ascending order when $S_{k+1}$ is even, and in descending order if $S_{k+1}$ is odd.

So the statement is true for all coordinates positions $i=2,\dots ,n$.    □

A convenient way to describe a Gray code is with the transition sequence [3,5], which is the ordered sequence of position changes from one word to the next. The transition sequence of a Gray code is an arrangement of positions showing the locations that undergo a change as one proceeds along the codewords. In most papers and books dealing with the transition sequence, the columns of $G_m\left(k\right)$ are numbered starting with 1 from right to left, but here, we number them as usual for matrices from left to right. In addition, because we consider a m-ary Gray code and the coordinates participate in decreasing and increasing subsequences, we multiply the current element in the transition sequence by $-1$ if the corresponding coordinate belongs to a decreasing subsequence. We denote the transition sequence for the reflected m-ary Gray code $G_m\left(n\right)$ by $T_m\left(n\right)$.

Example 1.

We give examples with a ternary and a quaternary reflected Gray codes.

• The ternary reflected Gray code of length 3 is given by the following sequence

  $$\begin{array}{cc}\hfill G_3\left(3\right)=& \{000,001,002,012,011,010,020,021,022,122,121,120,110,111,112,102,101,\hfill \\ \hfill & 100,200,201,202,212,211,210,220,221,222\}.\hfill \end{array}$$
  Its transition sequence is

  $$T_3\left(3\right)=(3,3,2,-3,-3,2,3,3,1,-3,-3,-2,3,3,-2,-3,-3,1,3,3,2,-3,-3,2,3,3).$$
• $G_4\left(2\right)=\{00,01,02,03,13,12,11,10,20,21,22,23,33,32,31,30\}$,
  $T_4\left(2\right)=(2,2,2,1,-2,-2,-2,1,2,2,2,1,-2,-2,-2)$.

In this paper, we present a C implementation of the algorithms. All of them use a global array g, in which the current codeword is written, and a global constant Maxn, which applies to all arrays in the algorithms and sets the maximum length of the code to generate. The function print is used to print the codewords and the corresponding values of the transition sequence to the screen (see Algorithm 1). We use this function in all programs to show that the next codeword is available.

Algorithm 1 The function print and the global variables

const int Maxn=30; int g[Maxn];   void print(int g[], int n, int t) {    for (int j = 1; j <= n; j++) { printf("%d", g[j]); }    printf(" T= %d; \n", t); }

The algorithms are unified, and in all of them, the arrays are denoted in the same way. The array S consists only of $\pm 1$, and indicates that when the corresponding coordinate will be in an ascending or descending sequence, the variable t indicates the corresponding value in the transition sequence, etc. The array S is optional, and in the implementation of the algorithms, we can choose whether to use this array or directly check whether the corresponding sum is even or odd (as shown in Theorem 1). We use both approaches in our algorithms. It is good to note that for an integer a we have $a\&1=0$ if a is even, and $a\&1=1$ if a is odd.

An algorithm that generates the set $G_m\left(n\right)$ is proposed in [4] and used in its original form in [5]. In Algorithm 2, we present its C implementation with an addition, namely checking that the same value is not written more than once. It is good to note that the original functions write the same values more than once, and so the number of recursive calls can reach ≈1.5$m^n$ ($1.5$ times the number of the generated codewords). It is important to note that it is not always $1.5$, but it is reached in the worst cases. As we already described, in g we put the currently generated codeword, m is the cardinality of the alphabet, and n is the length of the code. The additional check that the same value is not written more than once does not increase the time complexity of Algorithm 2—it remains $\mathsf{\Omega }\left(m^n\right)$.

Algorithm 2 Generates the sequence $G_m\left(n\right)$ by indirect recursion

void Gray_rec_refl (int k, int m, int n); // a function~prototype   void Gray_rec (int k, int m, int n) {    if (k <= n) {       for (int j = 0; j <= m - 1; j++) {          if (g[k] != j) {             g[k] = j; int t = k; print (g, n, t);          }          if (j & 1)  Gray_rec_refl (k +1, m, n);  // when j is odd          else  Gray_rec (k + 1, m, n);       }    } }   void Gray_rec_refl (int k, int m, int n) {    if (k <= n) {       for (int j = m - 1; j >= 0; j--) {          if (g[k] != j) {             g[k] = j; int t = -k; print (g, n, t);          }          if (j & 1)  Gray_rec (k + 1, m, n);          else  Gray_rec_refl (k + 1, m, n);       }    } } void main_rec_refl (int m, int n) {    for (int i = 0; i <= n; i++) { g[i] = 0; }    print (g, n, 0);    Gray_rec (1, m, n); }

The algorithms in [4] have redundant steps, so we offer other variants that are based on a nested loop algorithm. In Algorithm 3, we present the variant for $n=4$ with four nested loops. This algorithm is intuitive and easy to understand, and moreover all subsequent algorithms can be explained through it.

The n nested loops algorithm is defined by: (1) the number of loops; (2) the counter values of each loop; (3) the sequence in which the loops are executed. In Algorithm 3, k-th loop changes the k-th coordinate in the current codeword of $G_m\left(n\right)$. In the reflected Gray code, there is another component indicating when to change sign in an iteration (which corresponds to the question of when to change the order of coordinates at a given position in successive codewords from ascending to descending and vice versa). It is essential for the sequence of loops that after each change of a coordinate (generation of another codeword), one goes to the innermost cycle (we mean that intermediate loops do nothing).

Algorithm 3 Nested loop algorithm for the reflected Gray code – example for $n=4$

void nested_loops_refl (int m, int n) {     int S[Maxn], t=0;     for (int i = 1; i <= n; i++) { g[i] = 0; S[i] = 1; }     for (int i1 = 1; i1 <= m; i1++) {         if (i1 > 1) { g[1] = g[1] + S[1]; t = S[1]; }         if (i1 == m) S[1] = -S[1];         for (int i2 = 1; i2 <= m; i2++) {           if (i2 > 1) { g[2] = g[2] + S[2]; t = 2*S[2]; }               if (i2 == m) S[2] = -S[2];           for (int i3 = 1; i3 <= m; i3++) {             if (i3 > 1) { g[3] = g[3] + S[3]; t = 3*S[3]; }             if (i3 == m) S[3] = -S[3];             for (int i4 = 1; i4 <= m; i4++) {                 if (i4 > 1) { g[4] = g[4] + S[4]; t = 4*S[4]; }                 if (i4 == m) S[4] = -S[4];                 print (g, n, t);             }           }         }     } }

Proof for the correctness of Algorithm 3 with n nested loops.

This algorithm uses the two arrays g and S. Recall that in g we store the current codeword of $G_m\left(n\right)$. The elements of S are plus and minus 1s and indicate whether we will get the next coordinates in the corresponding position in ascending or descending order. If $S\left[i\right]=1$, then the algorithm generates the i-th coordinate in ascending order, and if $S\left[i\right]=-1$—in descending order. Hence, changing the sign in $S\left[i\right]$, we change the order.

We will prove that this algorithm generates the reflected Gray code as defined in (1) by induction. If $n=1$, the algorithm has only one cycle and generates $G_m\left(1\right)$.

Suppose that the algorithm with $k-1<n$ nested loops generates $G_m(k-1)$ and consider the algorithm with k nested cycles. If $i1=1$, then $S\left[i\right]=1$ for all $i=1,\dots ,n$ and so the other nested loops generate the reflected Gray code of length $k-1$. Further, when $i1$ takes value 2, the last values of $S\left[2\right]$, $S\left[3\right],\dots ,S\left[k\right]$ after the change have not yet been used, and therefore the algorithm in this part generates the mirror image of $G_m(k-1)$ which is $G_m^{\ast }(k-1)$. Whenever $i1$ changes, the algorithm generates a mirror image of the reflected Gray code of length $k-1$ generated at the previous value of $i1$. Thus, we have the same recursive construction as in Definition 1.    □

The following algorithms reduce the number of operations to obtain the next codeword, each with its own advantages. Algorithm 4 presents a recursive version of the nested loop algorithm. There are two recursive calls in the recursive procedure. The first call serves to reach the last level (bottom) of the recursion (i.e., the innermost loop in the nested loop variant). In Algorithm 4, the array S is not used, but the sum $S_i$ from Theorem 1 is directly checked whether it is even or odd. This algorithm can also be implemented using the array S, in which case there would be no need for the sum $ss$ and the variable s.

For recursive algorithms (in both sections), the depth of the recursive entries corresponds to the number of the nested loops. In Algorithm 4, the variable h indicates the current depth in the recursion and takes values from 1 to $n+1$, but if $h=n+1$, the algorithm does nothing and simply goes back one step in the recursion.

Algorithm 4 Recursive generation of $G_m\left(n\right)$

void Gray_refl_rec (int h, int ss, int m, int n) {    if (h <= n) {       Gray_refl_rec (h + 1, (ss + g[h]) & 1, m, n);       int  s = 1 + (-2) * ss;       for (int i = 0; i < m - 1; i++) {          g[h] = g[h] + s;          int t = h * s;  print(g, n, t);          Gray_refl_rec (h + 1, (ss + g[h]) & 1, m, n);       }    } } void main_Gray_refl_rec (int m,int n) {    for (int i = 0; i <= n; i++)  g[i] = 0;    print(g, n, 0);    Gray_refl_rec (1, 0, m, n); // ss = 0 in the beginning }

A short and simple non-recursive algorithm for generating the sequence $G_m\left(n\right)$ is presented in [10]. It is derived after the proof of three theorems. Here we propose a similar algorithm derived in a simpler way. The idea is to modify each of the nested loops to perform reflection. When the loop variable reaches its final value $m-1$, it should continue with its reflection, i.e., its values must decrease from $m-1$ to 0 after increasing from 0 to $m-1$, and vice versa—when the loop variable decreases and reaches its final value 0, the reflection ends and the loop variable starts increasing again from 0 to $m-1$. We keep the arrays g for the current codeword (vector) of $G_m\left(n\right)$ and S, but add one additional array final_vals of the same type. The element final_vals[j] stores the limit value of the jth cycle, which is $m-1$ when the jth coordinate increases (i.e., S[j]=1), or 0 when this coordinate decreases (i.e., S[j]= -1), for $j=1,2,\dots ,n$. The C code of this algorithm is presented in Algorithm 5.

Algorithm 5 Non-recursive generation of $G_m\left(n\right)$

void Gray_refl_nonrec (int m, int n) {    int S[Maxn], final_vals[Maxn], k, t = 0;    for (int i = 0; i <= n; i++) { //initialization:       g[i] = 0;      // current codeword       S[i] = 1;      // steps to change the coordinates       final_vals[i] = m - 1; // final values of the coordinates    }    do {       print (g,n,t);       k = n;       while (g[k] == final_vals[k]) {          S[k] = -S[k];          if (S[k] < 0)  final_vals[k] = 0;          else  final_vals[k] = m - 1;          k--;       }       g[k] = g[k] + S[k]; t = k * S[k];    } while (k > 0); }

As can be seen, the algorithm continues until all elements of the array g reach their limit values (the limit value is 0 or $m-1$). Then, the value of S[1] should reverse to $-1$ and the algorithm terminates, as the main loop do...while indicates. Through the (inner) while loop, the algorithm scans from right to left the elements of the array g, looking for an element that has not reached its final value. Meanwhile, for all elements $g\left[k\right]$ with limit values, the corresponding elements $S\left[k\right]$ reverse their signs and, depending on the sign, the corresponding elements final_vals[k] get required value: $m-1$ or 0. The advantage of this algorithm (comparing with Algorithm 3) is that when at some step the sign of $S\left[k\right]$ needs to be changed, the signs of the following elements of the array S are changed along with it, i.e., $S[k+1],\dots ,S\left[n\right]$.

The correctness of this algorithm follows from Definition 1 and the way of emulating the execution of n nested loops. It corresponds to Theorem 1 and can be proved analogously by induction on n. Regarding its time complexity, apparently, the algorithm performs $O\left(n\right)$ operations to generate each vector after the current one. Regarding the exact estimate of the time complexity, we note that the while loop runs in total $(m^n+m^{n-1}+\cdots +m)=(m^{n+1}-m)/(m-1)=\mathsf{\Theta }\left(m^n\right)$ times [2]. For each run, it performs 2 comparisons, 3 assignments, one subtraction, and one sign change. Thus, the while loop performs $\mathsf{\Theta }\left(m^n\right)$ operations. In the body of the main loop do…while, more $\mathsf{\Theta }\left(m^n\right)$ comparisons, assignments, and additions are performed (excluding print operations). Therefore, the total time complexity of Algorithm 5 is $\mathsf{\Theta }\left(m^n\right)+\mathsf{\Theta }\left(m^n\right)=\mathsf{\Theta }\left(m^n\right)$ and the average time to generate one vector is constant; hence, it is a constant amortized-time (CAT) algorithm [7].

In [11], the authors used stack to generate the code and the transition sequence, but only in the binary case. The stack operates as follows: the stack initially contains $n,n-1,\dots ,1$ (with 1 on top). The algorithm pops off the top element i and puts it into the transition sequence (respectively changes the corresponding coordinate in the current codeword); the elements $i-1,i-2,\dots ,1$ are then pushed onto the stack. The stack operates in a highly restricted manner since when $j>1$ is placed in the stack, we know a priori that $j-1,\dots ,1$ will be placed above it.

In this implementation, each subsequent codeword is obtained after a constant number of operations and so Algorithm 6 is a loopless algorithm (for loopless algorithms see [2,11]). In Figure 1 and Figure 2, we have graphically presented how the algorithm works.

The implementation of Algorithm 6 is carried out in a very elegant way by using a single array. We give a generalization of the algorithm for the m-ary reflected Gray code, and when $m>2$ we need the additional array M. In each cell of the stack, there are initially m elements, which are taken one by one. As can be seen, Algorithm 6 performs a constant number of operations to generate each subsequent codeword, regardless of n and m.

Algorithm 6 Generation of $G_m\left(n\right)$ using a stack

void refl_stack (int m, int n) {    int S[Maxn], T[Maxn], M[Maxn];    int i, j, t;    for (int j = 0; j <= n; j++) { // initialization       T[j] = j + 1;       M[j] = m-1;       S[j] = 1;       g[j] = 0;    }    i = 1;    print (g,n,0);    do {       j = n + 1 - i;       g[j] = g[j] + S[i]; t = j*S[i];       print (g, n, t);       M[i] = M[i] - 1;       T[0] = 1;       if (0 == M[i]) {          T[i - 1] = T[i];          T[i] = i + 1;          M[i] = m - 1;          S[i] = -S[i];       };       i = T[0];    } while (i != n + 1); }

The functions for computing the predecessor and successor, for ranking and unranking play an important role in the generation of combinatorial objects, as it is noted in [2,7,12] and others. Most authors consider these functions when generating given combinatorial objects. In Gray codes, the ranking and unranking functions are of particular importance and we also consider them in this work.

For ranking, we assign to each codeword in the reflected Gray code its sequence number, starting from 0 and ending with $m^n-1$ (ordinal ranking, row numbering). Let $g=(g_1,g_2,\cdots ,g_n)$ be a codeword in $G_m\left(n\right)$. It is easier to obtain its sequence number, if we use the m-ary representation of the non-negative integers (the representation in a numeral system of base m). Let $a_g$ be the rank (row number) of the vector $g\in G_m\left(n\right)$ and $a_1,\dots ,a_n$ are the digits of the integer $a_g$ in the m-ary numeral system, where $a_g=a_1{m}^{n-1}+a_2{m}^{n-2}+\cdots +a_n$. It is easy to see that $a_1=g_1$. We give the relation between g and $a_g$ in the following theorem.

Theorem 2.

Let $g=(g_1,\cdots ,g_n)\in G_m\left(n\right)$ be a codeword in the reflected Gray code and $a_g$ be its sequence number. If $a_g=a_1{m}^{n-1}+a_2{m}^{n-2}+\cdots +a_n$, $0\le a_i\le m-1$, $i=1,\dots ,n$, then

$$\begin{array}{c}\hfill a_i=\left\{\begin{array}{c}{g}_i, \mathit{if} S_i \mathit{is} \mathit{even},\hfill \\ m-1-g_i,\mathit{if} S_i \mathit{is} \mathit{odd},\hfill \end{array}\right.\end{array}$$

(2)

where $S_1=0$ and $S_i={\sum }_{j=1}^{i-1}{g}_j$ for $2\le i\le n$.

Proof. 

Again, we use induction on n. If $n=1$, $G_m\left(1\right)={(0,1,\dots ,m-1)}^T,$ and the corresponding numbers are $0,1,\dots ,m-1$, so $a_g=g_1$. Assume that the statement is true for $G_m(n-1)$, and take $g=(g_1,\dots ,g_n)\in G_m\left(n\right)$. If $g_1=0$, then $a_g$ coincides with the number of the codeword $(g_2,\dots ,g_n)\in G_m(n-1)$. Since in this case $S_i={\sum }_{j=1}^{i-1}{g}_j={\sum }_{j=2}^{i-1}{g}_j$, the Formula (2) holds for the codeword g. In the general case, $a_g=g_1{m}^{n-1}+a_g^{\prime }$, where $a_g^{\prime }$ is the rank of $g^{\prime }=(g_2,\dots ,g_n)\in G_m(n-1)$ if $g_1$ is even, and $g^{\prime }=(g_2,\dots ,g_n)\in G_m^{\ast }(n-1)$ if $g_1$ is odd. If $S_i^{\prime }=S_i-g_1={\sum }_{j=2}^{i-1}{g}_j$, then $S_i\equiv S_i^{\prime }(mod2)$ if $g_1$ is even, and $S_i\equiv S_i^{\prime }+1(mod2)$ if $g_1$ is odd. Hence, if $g_1$ is even, then

$$a_i=\left\{\begin{array}{c}{g}_i, \mathrm{if} S_i \mathrm{is} \mathrm{even},\hfill \\ m-1-g_i,\mathrm{if} S_i \mathrm{is} \mathrm{odd},\hfill \end{array}\right..$$

If $g_1$ is odd, then $g^{\prime }=(g_2,\dots ,g_n)\in G_m^{\ast }(n-1)$ and in this case the codewords of the corresponding Gray code are taken in reverse order. Hence, the number of $g^{\prime }$ if this code is $m^{n-1}-1-a_{g^{\prime }}$, where $a_{g^{\prime }}$ is the number of $g^{\prime }\in G_m(n-1)$. Since the ciphers of this number for radix m are $m-1-a_2,m-1-a_3,\dots ,m-1-a_n$, we have the same formula for $a_i$, $i=1,\cdots ,n$.    □

Corollary 1.

Let $a=a_1{m}^{n-1}+a_2{m}^{n-2}+\cdots +a_n$, $0\le a_i\le m-1$, $i=1,\dots ,n$, be a nonnegative integer, $0\le a\le m^n-1$, and $g=(g_1,g_2,\dots ,g_n)$ be the codeword in $G_m\left(n\right)$ in the a-th row according to Definition 1. Then

$$\begin{array}{c}\hfill g_i=\left\{\begin{array}{c}{a}_i, \mathit{if} S_i \mathit{is} \mathit{even},\hfill \\ m-1-a_i, \mathit{if} S_i \mathit{is} \mathit{odd}.\hfill \end{array}\right.\end{array}$$

(3)

where $S_1=0$ and $S_i={\sum }_{j=1}^{i-1}{g}_j$ for $2\le i\le n$.

Table 1. Ranking for the codewords in $G_3\left(3\right)$.

Number	Number	Codeword	Number	Number	Codeword
(Rank)	(Radix 3)		(Rank)	(Radix 3)
0	000	000	14	112	112
1	001	001	15	120	102
2	002	002	16	121	101
3	010	012	17	122	100
4	011	011	18	200	200
5	012	010	19	201	201
6	020	020	20	202	202
7	021	021	21	210	212
8	022	022	22	211	211
9	100	122	23	212	210
10	101	121	24	220	220
11	102	120	25	221	221
12	110	110	26	222	222
13	111	111

and

Table 2. Ranking for the codewords in $G_4\left(2\right)$.

Number	Number	Codeword	Number	Number	Codeword
(Rank)	(Radix 4)		(Rank)	(Radix 4)
0	00	00	8	20	20
1	01	01	9	21	21
2	02	02	10	22	22
3	03	03	11	23	23
4	10	13	12	30	33
5	11	12	13	31	32
6	12	11	14	32	31
7	13	10	15	33	30

show the ranking of the codewords in $G_3\left(3\right)$ and $G_4\left(2\right)$, respectively. The implementation of the Formulas (2) and (3) is given in Algorithm 7. Additionally, we have incorporated the decimal representation of the rank (sequence number) into these algorithms. Obviously, each of the rank and unrank functions runs in $\mathsf{\Theta }\left(n\right)$ time.

Algorithm 7 Ranking and unranking for the reflected Gray code

void Gray_refl_unrank (int g[], int m, int n, int value) {    int a[Maxn];    for (int i = 0; i < n; i++) {       a[n-i] = value % m;       value = value / m;    }    g[1] = a[1];    int sum = g[1];    for (int i = 2; i <= n; i++) {       if (sum & 1)  g[i] = m - 1 - a[i];       else  g[i] = a[i];       sum = sum + g[i];    } }   int Gray_refl_rank (int g[], int m, int n) {    int a[Maxn];    a[1] = g[1];    int sum = g[1];    for (int i = 2; i <= n; i++) {       if (sum & 1)  a[i] = m - 1 - g[i];       else  a[i] = g[i];       sum = sum + g[i];    }    int value = 0, mm = 1;    for (int i = n; i >= 1; i--) {       value = value + mm * a[i];       mm = mm * m;    }    return value; }

Algorithm 8 is very convenient if one wants to generate only a part of the codewords, namely the codewords from A to B, where $0\le A<B\le m^n-1$. The main thing in it is to find a codeword by a given number in the sequence (unranking). We follow the algorithm for $G_2\left(n\right)$ from [13], but present an extended version for the m-ary Gray code.

Its time complexity analysis is similar to that of Algorithm 5 or can be used as a generalization of that in [13]. Finally, we get that Algorithm 8 is again a CAT algorithm.

Algorithm 8 Part of the reflected Gray code

void Gray_refl_from_A_to_B (int m, int n, int A, int B) {    Gray_refl_unrank (g, m, n, A);    int S[Maxn];    int i = A, j, k, br = A, sum = 0, t=0;    S[1] = 1;    for (int j = 2; j <= n; j++) {       sum = sum + g[j - 1] & 1;       if (0 == sum)  S[j] = 1;       else S[j] = -1;    }    do {       print (g, n, t);       if (B == br)  return;       k = n;       i = i + 1;       j = i;       while (0 == (j % m)) {          j = j / m; k = k - 1;       }       if (k > 0) {          int temp = g[k] + S[k];          if ((temp < 0) || (temp == m)) { S[k] = -S[k]; }          g[k] = g[k] + S[k]; br++; t = k * S[k];       }    } while (k > 0); }

3. The $\mathit{m}$-Ary Modular (Shifted) Gray Code

In [3], the authors define the directional distance of b from a, where $a,b\in {\mathbb{Z}}_m$, denoted by $\sigma (b-a)$ and equal to $(b-a)(modm)$. Next, they define the directional distance of a vector from another vector in ${\mathbb{Z}}_m^n$ as the sum of directional distances between their respective components, or 

$$d_D(u,v)=\sum _{i=1}^n\sigma (b_i-a_i),u=(a_1,\dots ,a_n),v=(b_1,\dots ,b_n)\in {\mathbb{Z}}_m^n.$$

It is worth mentioning that the directional distance is not a metric in ${\mathbb{Z}}_m^n$ because there are vectors $u,v\in {\mathbb{Z}}_m^n$, such that $d_D(v,u)\ne d_D(u,v)$. In [3], ([Lemma 1]), it was proved that $d_D(v,u)+d_D(u,v)=m{d}_H(u,v)$, where $d_H$ is the Hamming distance between the vectors.

In this section, we study the m-ary Gray code defined in [3] as an ordered sequence of the vectors of ${\mathbb{Z}}_m^n$, such that each vector differs from the preceding vector by directional distance one. This means that to obtain the next codeword, we add one modulo m to exactly one coordinate and do not change the other coordinates. We denote the thus-defined code that starts from the zero vector by $G(m,n)$ and call it a modular (or shifted) Gray code. In the m-ary modular Gray code, the m-ary vectors are ordered such that every two consecutive vectors differ by exactly one coordinate, and the difference is $+1$ modulo m. If $m=2$, this Gray code coincides with the reflected Gray code, so we can consider it as another generalization of the binary reflected Gray code. We present the ternary modular Gray code of length 3 in

Table 3. Ranking for the codewords in $G(3,3)$.

Number	Number	Codeword	Number	Number	Codeword
(Rank)	(Radix 3)		(Rank)	(Radix 3)
0	000	000	14	112	101
1	001	001	15	120	111
2	002	002	16	121	112
3	010	012	17	122	110
4	011	010	18	200	210
5	012	011	19	201	211
6	020	021	20	202	212
7	021	022	21	210	222
8	022	020	22	211	220
9	100	120	23	212	221
10	101	121	24	220	201
11	102	122	25	221	202
12	110	102	26	222	200
13	111	100

.

A formula how from the m-adic representation of the integer a to obtain the corresponding codeword $g=(g_1,\dots ,g_n)\in G(m,n)$ is given in [3]. If $a=a_1{m}^{n-1}+a_2{m}^{n-2}+\cdots +a_n$, $0\le a_i\le m-1$, $i=1,\dots ,n$, then

$$\begin{array}{c}\hfill g_i=\left\{\begin{array}{c}{a}_i, \mathrm{if} i=1,\hfill \\ m-a_{i-1}+a_i(modm), \mathrm{if} i\ge 2.\hfill \end{array}\right.\end{array}$$

(4)

Conversely, we have

$$a_i=\sum _{j=1}^i{g}_i(modm).$$

(5)

Algorithm 9 implements these formulas with $\mathsf{\Theta }\left(n\right)$ running time.

The authors in [3] also present a generating recursive procedure for the code. As in the previous section, we again use the matrix representation of the codes. Obviously,

$$G(m,1)=G_m\left(1\right)={(0,1,\dots ,m-1)}^T.$$

Let

$$G^{\left(i\right)}(m,1)={(m-i,m-i+1,\dots ,m-i-1)}^T,i=1,\dots ,m,$$

be obtained on cyclically shifting of the elements of $G(m,1)$ by i positions. Then

$$G(m,2)=\left(\begin{array}{cc}0& \\ ⋮& G(m,1)\\ 0& \\ 1& \\ ⋮& G^{\left(1\right)}(m,1)\\ 1& \\ 2& \\ ⋮& G^{\left(2\right)}(m,1)\\ 2& \\ ⋮& ⋮\\ m-1& \\ ⋮& G^{(m-1)}(m,1)\\ m-1& \end{array}\right).$$

(6)

Algorithm 9 Ranking and unranking for the modular Gray code

void Gray_modular_unrank (int g[], int m, int n, int num) {    int a[Maxn];    for (int i = 0; i < n; i++) {       a[n-i] = num % m;       num = num / m;    }    g[1] = a[1];    for (int i = 2; i <= n; i++) {       g[i] = (m - a[i - 1] + a[i]) % m;    } }   int Gray_modular_rank (int g[],int m, int n) {    int a[Maxn];    for (int i = 1; i <= n; i++) {       a[i] = 0;    }    a[1] = g[1];    for (int i = 2; i <= n; i++) {       a[i] = (a[i-1]+g[i]) % m;    }    int num = 0;    int mm = 1;    for (int i = n; i >0; i--) {       num = num + a[i]* mm;       mm = mm * m;    }    return num; }

If $g_0(m,n),g_1(m,n),\dots ,g_{m^n-1}(m,n)$ are the codewords in $G(m,n)$, we define

$$G^{\left(k\right)}(m,n)={(g_0^{\left(k\right)}(m,n),g_1^{\left(k\right)}(m,n),\dots ,g_{m^n-1}^{\left(k\right)}(m,n))}^T,1\le k\le m-1,$$

where

$$g_i^{\left(k\right)}(m,n)=g_i(m,n)+k{g}_{m^n-1}(m,n)(modm),0\le i\le m^n-1.$$

Then we have the following matrix for $G(m,n)$

$$G(m,n)=\left(\begin{array}{cc}0& \\ ⋮& G(m,n-1)\\ 0& \\ 1& \\ ⋮& G^{\left(1\right)}(m,n-1)\\ 1& \\ 2& \\ ⋮& G^{\left(2\right)}(m,n-1)\\ 2& \\ ⋮& ⋮\\ m-1& \\ ⋮& G^{(m-1)}(m,n-1)\\ m-1& \end{array}\right).$$

(7)

The last codeword $g_{m^n-1}(m,n)$ in $G(m,n)$ is the last row in the above matrix, namely $(m-1,g_{m^{n-1}-1}^{(m-1)}(m,n-1))$. Since

$$\begin{array}{cc}\hfill g_{m^{n-1}-1}^{(m-1)}(m,n-1)& =g_{m^{n-1}-1}(m,n-1)+(m-1)g_{m^{n-1}-1}(m,n-1)(mod)m\hfill \\ \hfill & =m{g}_{m^{n-1}-1}(m,n-1)(modm)=(0,0,\dots ,0),\hfill \end{array}$$

then $g_{m^n-1}(m,n)=(m-1,0,0,\dots ,0)$. Hence, the modular Gray code $G(m,n)$ is cyclic.

The transition sequence for this Gray code is similar to the transition sequence $T_m\left(n\right)$ of the reflected Gray code $G_m\left(n\right)$, as the only difference is that we do not use negative numbers here. If $T(m,n)$ is the transition sequence for the code $G(m,n)$, then

$$T(m,n)=|T_m\left(n\right)|=(|t_0|,|t_1|,\dots ,|t_{m^n-1}\left|\right),$$

where $T_m\left(n\right)=(t_0,\dots ,t_{m^n-1})$.

Algorithm 10 generates the modular Gray code using nested loops. This algorithm repeats Algorithm 3 to generate the corresponding Gray code with nested loops, but in a simpler version, as the modular Gray code does not need the array S to change the sign. Instead, we add 1 modulo m to the corresponding coordinate. The proof of the correctness of Algorithm 10 is similar to the proof of the nested loop algorithm for the reflected Gray code (Algorithm 3). Its implementation using recursion is given in Algorithm 11.

Algorithm 10 Nested loop algorithm for the modular Gray code – example for $n=4$

void nested_loops_modular (int m, int n) {    int t = 0;    for (int i = 1; i <= 4; i++) { g[i] = 0; }    for (int i1 = 0; i1 <= m-1; i1++) {       if (i1 > 0) { g[1] = (g[1]+1) % m; t = 1; }       for (int i2 = 0; i2 <= m-1; i2++) {          if (i2 > 0) { g[2] = (g[2]+1) % m; t = 2; }          for (int i3 = 0; i3 <= m-1; i3++) {             if (i3 > 0) { g[3] = (g[3] + 1) % m; t = 3; }             for (int i4 = 0; i4 <= m-1; i4++) {                if (i4 > 0) { g[4] = (g[4] + 1) % m; t = 4; }                print(g,n,t);             }          }       }    } }

Algorithm 11 Recursive generation of $G(m,n)$

void Gray_modular_rec (int k, int n, int m) {    if (k <=n) {       Gray_modular_rec (k + 1, n, m);       for (int i = 1; i <= m - 1; i++) {          g[k] = (g[k] + 1) % m;  int t = k;          print (g, n, t);          Gray_modular_rec (k + 1, n, m);       }    } } void main_Gray_modular_rec (int m, int n) {    for (int i = 0; i <= n; i++)  g[i]=0;    print (g, n, 0);    Gray_modular_rec (1, n, m); }

As in Section 2, we present a non-recursive version of the algorithm for generating the modular Gray code (see Algorithm 12). This algorithm emulates the nested loops from Algorithm 10. The element current[k] of the additional array current shows the value of the k-th loop variable, $k=1,\dots ,n$. In the beginning, all values in current are zeros. The value of current[n] is then incremented by 1 at each subsequent step, and when it becomes equal to $m-1$, current[n − 1] increases by 1. Next, current[n] takes a zero value again and starts to increase to $m-1$. After that, again, current[n-1] increases by 1, and the same procedure repeats until $current\left[n\right]=current[n-1]=m-1$. Then, $current[n-2]$ starts increasing, etc. So, as in Algorithm 10, when $current\left[k\right]$ (or $ik$) is incremented by 1, then subsequent (inner) loops start over (i.e., from value 0).

Algorithm 12 uses an additional variable $np$. If $np$ is set to be 0, then the algorithm generates the modular Gray code $G(m,n)$, but if $np=1$ then it generates only non-proportional vectors, as described below. The time complexity analysis of Algorithm 12 is analogous to that of Algorithm 5. Its complexity is also $\mathsf{\Theta }\left(m^n\right)$, but Algorithm 12 is faster because it does not use arrays for signs and final (limit) values.

Algorithm 12 Non-recursive generation of $G(m,n)$

void Gray_modular_nonrec (int m, int n,int np) {    // np=0 - all codewords; np=1 - only nonproportional codewords    int current[Maxn];    for (int i = 1; i <= n; i++) {       if (0 == np)  current[i] = 0;       else  current[i] = m-2;       g[i] = 0;    }    current[0] = -1;    int k, t = 0;    do {       if ((t != 0) || (0 == np))  print (g, n, t);       k= n;       while (current[k] == m-1) { current[k]= 0; k--; }       current[k] ++;       g[k]= (g[k] + 1) % m;       t = k;    } while (k > 0); }

Algorithm 13 uses the function Gray_modular_unrank, presented in Algorithm 9, to list all codewords of the modular Gray code $G(m,n)$ from rank A to rank B, where $0\le A<B\le m^n-1$.

Algorithm 13 Part of the modular Gray code

void Gray_modular_from_A_to_B (int m, int n, int a, int b) {    Gray_modular_unrank (g, m, n, a);    int i = a, j, k, br = 0, t = 0;    do {       print (g, n, t);       if (br == b - a)  return;       k = n;       i = i + 1;       j = i;       while (0 == (j % m)) {          j = j / m; k = k - 1;       }       if (k > 0) {          g[k] = (g[k] + 1) % m; t =  k;       }       br++;    } while (k >0); }

In the end, we present an algorithm that generates only nonproportional vectors from ${\mathbb{Z}}_m^n$ in a Gray code. Let $S_m\left(n\right)$ be the set of all vectors in ${\mathbb{Z}}_m^n$ whose first nonzero coordinate is 1. For example,

$$S_3\left(3\right)=\{001,010,011,012,100,101,102,110,111,112,120,121,122\}.$$

Denote by $G(m,n,1)$ the modular Gray code after adding $+1$ modulo m to the first coordinate in each codeword, and consider the following recursive construction:

$$H_m\left(1\right)=\left(1\right),H_m\left(n\right)=\left(\begin{array}{cc}0& \\ ⋮& H_m(n-1)\\ 0& \\ 1& \\ ⋮& G(m,n-1,1)\\ 1& \end{array}\right).$$

(8)

First, we will give one example, and then we will prove that the presented construction generates a Gray code over $S_m\left(n\right)$.

Example 2.

We present the matrix for $m=n=3$.

$$H_3\left(3\right)={\left(\begin{array}{c}0000111111111\\ 0111111222000\\ 1120012201120\end{array}\right)}^T$$

Theorem 3.

The rows of the matrix $H_m\left(n\right)$ form a Gray code with $\frac{m^n-1}{m-1}$ codewords from the set $S_m\left(n\right)$.

Proof. 

Obviously,

$$H_m\left(2\right)=\left(\begin{array}{cc}0& 1\\ 1& 1\\ 1& 2\\ ⋮& ⋮\\ 1& m-1\\ 1& 0\end{array}\right)$$

represents a Gray code. Assume that $H_m(n-1)$ forms a Gray code. By the induction hypothesis, each vector $h_i$ differs from the preceding vector by directional distance one, where $h_i$ is the i-th row of the matrix $H_m\left(n\right)$ given in (8), for $2\le i\le \frac{m^{n-1}-1}{m-1}$. Since $G(m,n-1)$ is a Gray code, the same is true for $i=\frac{m^{n-1}-1}{m-1}+2,\dots ,\frac{m^n-1}{m-1}$. To complete the proof, we have to compare the last codeword in $(0,H_m(n-1))$ and the first one in $(1,G(m,n-1,1\left)\right)$. The first vector in $G(m,n,1)$ is $(1,0,\dots ,0)$ and the last one is $(0,0,\dots ,0)$. Since $H_m(n-1)$ is generated by the same construction, its last row is $(1,0,\dots ,0)$. Hence, the rows with numbers $\frac{m^{n-1}-1}{m-1}-1$ and $\frac{m^{n-1}-1}{m-1}$ in $H_m\left(n\right)$ are $(0,1,0,\dots ,0)$ and $(1,1,0,\dots ,0)$. They differ only in the first coordinate and therefore they are consecutive codewords and $H_m\left(n\right)$ forms a Gray code.    □

Example 3.

We present one more example, namely the Gray code $H_4\left(3\right)$.

$${\left(\begin{array}{c}000001111111111111111\\ 011111111222233330000\\ 112300123301223011230\end{array}\right)}^T$$

Algorithm 14 directly follows the recursive construction (8).

Algorithm 14 Gray code with non-proportional vectors

void Gray_modular_nonproportional (int m, int n) {    for (int j = n; j > 0; j--) {       for (int i = 0; i <= n; i++)  g[i]=0;       g[j] = 1;       if (j == n)  print (g, n, j);       else {          for (int i = 1; i <= m; i++) {             g[j + 1] = i % m;             print (g, n, j+1);             Gray_modular_rec (j + 2, n, m);          }       }    } }

Recall that Algorithm 12 generates the same Gray code with non-proportional vectors from ${\mathbb{Z}}_m^n$, when $np$ is set to 1. In this case, the initial values of the elements of the array $current$ are set to $m-2$.

The final implementation presents an algorithm that can generate the modular Gray code with all vectors from ${\mathbb{Z}}_m^n$ or only with non-proportional among them. This depends on the value of the parameter $np$, so if $np=0$ then the algorithm generates all vectors, and if $np=1$, it generates a maximal set of non-proportional vectors from ${\mathbb{Z}}_m^n$. Similarly to Algorithm 6, Algorithm 15 presents a generalization of the implementation by stack from [11] for the modular m-ary Gray code. Here too, as in Algorithm 6, we use the arrays T and M, and the initial value of the array M is $(m-1,\dots ,m-1)$ if $np=0$ and $(1,\dots ,1)$ if $np=1$. The difference between both algorithms for the generation of the Gray code with all vectors from ${\mathbb{Z}}_m^n$ is that for the reflected Gray code, we have the array S with plus and minus ones used for the change of the sign in the transition sequence, but in the modular Gray code there is no such an array, the integers in the transition sequence are only positive, and any change (of a coordinate) is adding $+1$ modulo m. If the initial value of the array M consists of ones, Algorithm 15 generates only non-proportional vectors. This nontrivial m-ary generalization of the stack algorithm is presented in [9]. It is easy to see that Algorithm 15 generates the same Gray code with non-proportional vectors from the set $S_m$ as Algorithm 14. Also, Algorithm 15 is a loopless algorithm.

Algorithm 15 Gray code with non-proportional vectors—generation by using stack

void Gray_modular_nonproportional_by_stack (int m, int n,int np) {    // np=0 - all codewords; np=1 - only nonproportional codewords    int  T[Maxn], M[Maxn];    int i, j, t;    for (int j = 0; j <= n; j++) {  // initialization       T[j] = j + 1;       if (1 == np)  M[j] = 1;       else  M[j] = m - 1;       g[j] = 0;    }    i = 1;    if (1 != np)  print (g, n, 0);    do {       j = n + 1 - i;       g[j] = (g[j] + 1) % m;       t = j;       print (g, n, t);       M[i] = M[i] - 1;       T[0] = 1;       if (0 == M[i]) {          T[i - 1] = T[i];          T[i] = i + 1;          M[i] = m - 1;       };       i = T[0];    } while (i != n + 1); }

Remark 1.

The presented algorithms are not optimized in order to be more understandable. For example, j=(j+1) % m (this is $j+1$ modulo m) is repeated many times, but can be replaced by the much more efficient if j==m-1 then j=0 else j=j+1.

4. Conclusions

In this paper, we present algorithms for generating reflected and modular (shifted) m-ary Gray codes. The idea for this work arose in connection with our software for the study of linear codes over various finite fields, the use of a Gray code being particularly important in programs for calculating the weight characteristics as minimum distance and weight distribution. We especially emphasize algorithms for generating part of the sequence in the Gray code with the idea that we can use them in a parallel implementation of some of our programs for computing parameters of linear codes over a finite field with q elements, where q is a prime power.

Some of the proposed algorithms are variants of already known ones, and others are generalizations of algorithms for generating binary Gray codes. Some of the algorithms produce the same result but have their advantages and disadvantages. 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 $\mathsf{\Theta }\left(m^4\right)$. In the general case, for n nested loops, they have a time complexity of the type $\mathsf{\Theta }\left(m^n\right)$.
• 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 $\mathsf{\Theta }\left(n\right)$.

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.