# Generating \(m\)-[PERSON] Gray Codes and Related Algorithms
## 3 The \(m\)-Ary Modular (Shifted) Gray Code
So, as in Algorithm 10, when \(current[k]\) (or \(ik\)) is incremented by \(1\), then subsequent (inner) loops start over (i.e., from value \(0\)). ```
voidGray_modular_rec(intk,intn,intn){  if (k <= n){  Gray_modular_rec(k+1,n,m);  for (int i = 0; i <= m-1; i++) {  g[k] = (g[k] + 1) X m; int t = k;  print (g, n, t);  Gray_modular_rec(k+1,n,m);  }  } }
```

**Algorithm 11** Recursive generation of \(G(m,n)\)

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 \(\Theta(m^{n})\), but Algorithm 12 is faster because it does not use arrays for signs and final (limit) values. ```
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] = n-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] == n-1) { current[k]= 0; k-; }  current[k] ++;  g[k]= (g[k] + 1) % m;  t = k;  } while (k > 0); }
```

**Algorithm 13** Part of the modular Gray code

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\leq A<B\leq m^{n}-1\). ```
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); }
```

**Algorithm 14** Part of the modular Gray code

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

\[S_{3}(3)=\{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}(1)=(1),\;\;H_{m}(n)= \begin{pmatrix}0&&\\ \vdots&H_{m}(n-1)\\ 0&&\\ \hline 1&&\\ \vdots&G(m,n-1,1)\\ 1&&\\ \end{pmatrix} . \tag{8}\]First, we will give one example, and then we will prove that the presented construction generates a Gray code over \(S_{m}(n)\). **Example 2**. : _We present the matrix for \(m=n=3\)._

\[H_{3}(3)= \begin{pmatrix}0000111111111\\ 0111111222000\\ 1120012201120\end{pmatrix} ^{T}\]

**Theorem 3**. : _The rows of the matrix \(H_{m}(n)\) form a Gray code with \(\frac{m^{n}-1}{m-1}\) codewords from the set \(S_{m}(n)\)._

Proof. : Obviously,

\[H_{m}(2)= \begin{pmatrix}0&1\\ 1&1\\ 1&2\\ \vdots&\vdots\\ 1&m-1\\ 1&0\end{pmatrix} \]

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}(n)\) given in (8), for \(2\leq i\leq\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,\ldots,\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))\). The first vector in \(G(m,n,1)\) is \((1,0,\ldots,0)\) and the last one is \((0,0,\ldots,0)\). Since \(H_{m}(n-1)\) is generated by the same construction, its last row is \((1,0,\ldots,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}(n)\) are \((0,1,0,\ldots,0)\) and \((1,1,0,\ldots,0)\).