# Generating \(m\)-[PERSON] Gray Codes and Related Algorithms
## 3 The \(m\)-Ary Modular (Shifted) Gray Code
\tag{6}\]  
void Gray_modular_unrank (int g[], int m, int n, int num) {  in a[Maxwell];  for (int i = 0; i < n; i++) {  a[n-1] = 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) {  in a[Maxwell];  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; } ```
**Algorithm 9** Ranking and unranking for the modular Gray code
``` void Gray_modular_unrank (int g[], int m, int n, int num) {  in a[Maxwell];  for (int i = 0; i <= n; i++) {  a[n-1] = 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



If \(g_{0}(m,n),g_{1}(m,n),\ldots,g_{m^{n}-1}(m,n)\) are the codewords in \(G(m,n)\), we define

\[G^{(k)}(m,n)=(g_{0}^{(k)}(m,n),g_{1}^{(k)}(m,n),\ldots,g_{m^{n}-1}^{(k)}(m,n))^{T},\,1\leq k\leq m-1,\]

where

\[g_{i}^{(k)}(m,n)=g_{i}(m,n)+kg_{m^{n}-1}(m,n)\pmod{m},\,0\leq i\leq m^{n}-1.\]

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

\[G(m,n)=\left( \begin{array}{ccc}0&&\\ \vdots&G(m,n-1)\\ 0&&\\ \hline 1&&\\ \vdots&G^{(1)}(m,n-1)\\ 1&&\\ \hline 2&&\\ \vdots&G^{(2)}(m,n-1)\\ 2&&\\ \hline\vdots&\vdots\\ \hline m-1&&\\ \vdots&G^{(m-1)}(m,n-1)\\ m-1&&\\ \end{array} \right). \tag{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

\[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)\pmod{m}\] \[=mg_{m^{n-1}-1}(m,n-1)\pmod{m}=(0,0,\ldots,0),\]

then \(g_{m^{n}-1}(m,n)=(m-1,0,0,\ldots,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}(n)\) of the reflected Gray code \(G_{m}(n)\), 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}(n)|=(|t_{0}|,|t_{1}|,\ldots,|t_{m^{n}-1}|),\]

where \(T_{m}(n)=(t_{0},\ldots,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. ```
voidnested_loops_modular(intm,intn){  int t = 0;  for (int i = 1; i <= 4; i++) { g[i] = 0; }  for (int i1 = 0; i <= m-1; i++) {  if (i1 > 0) { g[i] = (g[i1]+) X m; t = 1; }  for (int i2 = 0; i2 <= m-1; i2++) {  if (i2 > 0) { g[2] = (g[2]+1) X m; t = 2; }  for (int i3 = 0; i3 <= m-1; i3++) {  if (i3 > 0) { g[3] = (g[3] + 1) X m; t = 3; }  for (int i4 = 0; i4 <= -1; i4++) {  if (i4 > 0) { g[4] = (g[4] + 1) X m; t = 4; }  print(g,n,t);  }  }  }  } }
```

**Algorithm 10** Nested loop algorithm for the modular Gray code - example for \(n=4\)

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,\ldots,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[n]=current[n-1]=m-1\). Then, \(current[n-2]\) starts increasing, etc.