# Generating \(m\)-[PERSON] Gray Codes and Related Algorithms
## 3 The \(m\)-Ary Modular (Shifted) Gray Code
They differ only in the first coordinate and therefore they are consecutive codewords and \(H_{m}(n)\) forms a Gray code. **Example 3**. : _We present one more example, namely the Gray code \(H_{4}(3)\)._

\[ \begin{pmatrix}0000011111111111111\\ 01111111122223330000\\ 112300123301223011230\end{pmatrix} ^{T}\]

Algorithm 14 directly follows the recursive construction (8). ```
voidGray_modular_nonproportional(intm,intn){ for(intj=n;j>0;j-){ for(inti=0;i<=n;i++)g[i]=0; g[j]=1; if(j==n)print(g,n,j); else{ for(inti=1;i<=n;i++){ g[j+1]=i%m; print(g,n,j+1); Gray_modular_rec(j+2,n,m); } } }
```

**Algorithm 14** Gray code with non-proportional vectorsRecall 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,\ldots,m-1)\) if \(np=0\) and \((1,\ldots,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. ```
voidGray_modular_nonproportional_by_stack(intm,intn,intnp){ //np=0-allcodewords;np=1-onlynonproportionalcodewords intT[Maxm],M[Maxm]; inti,j,t; for(intj=0;j<=n;j++){ //initialization T[j]=j+1; if(1==npM[j]=1; elseM[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;  v =j; print(g,n,t); M[i]=M[i]-1; T[0]=1; if(0==M[i]){ T[i-1]=T[i]; T[i]=1+1; M[i]=m-1; }; i =T[0]; } while(i!=n+1); }
```

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

**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.