从二进制格雷码到任意进制格雷码(2)

1. 概要

在从二进制格雷码到任意进制格雷码(1)中给出了4种二进制格雷码的生成方式，但是实际上，前三种都是利用了二进制格雷码的已知码结构特征的特殊的生成方法。这些生成方法没有通用性，因为它们是属于事后诸葛亮式，是先设计出了格雷码，然后再根据码的结构特征写出各种技巧性的代码。而且它们也仅仅代表了很多种可能的二进制格雷码中的特殊的一种（当然也是最常用的一种）而已。

只有最后一种方法是从基本定义（the first principle）出发的生成方法，是具有通用性的。而且，即便是二进制的格雷码，也有很多种设计方式，以上各种生成方法只代表了其中一个特定的方法（当然也是最常用的一种）。

本篇将格雷码推广到任意M进制，并给出任意M进制的格雷码的生成方式。任意M进制格雷码没有（最常用的）二进制格雷码那种明显的结构特征，因此无法以各种极具技巧性的方式来进行构造。

2.任意M进制格雷码的表示

在二进制中编码的数字码元有{0，1}两种，在十进制中的数字码元则为{0,1,2,...,9}，在16进制中数字码元则在十进制的基础上追加了A,B, ... ,F分别表示10,11, ... ,15。在任意M进制的情况，像16进制那样用字母扩展的方式来扩展数字码元集并不明智（想一想比如说53进制，难道用0~9再加43个大小写混用的字母？），所以这里就直接使用{0,1, .... ,M-1}表示M进制的数字码元。比如说37进制的数字码元为{0,1,2, ... ,36}，在这里，36是作为一个数字码元来来使用，而不是一个十进制中的两位数。

其次，基于以上所述的数字码元的表达方式，一个M进制数（不管是自然码还是格雷码）自然就无法像二进制或者十进制或者十六进制那样紧凑地表示成0b101110, 12346, 0x1689ABC的形式了，因为任意M进制中的数字码元并不限于只包含一个字符。在本文中用十进制数列表来表示任意M进制的编码，比如说{1,16,2,13,5,2}表示一个17进制的6位数。与常规的二进制、十进制和十六进制表示一样，左边表示高位，右边表示低位。

3. 低位优先更新法—深度优先搜索

基于上一篇的算法稍作修改（扩展，generalization）可以得到基于深度优先搜索的面向M进制n位格雷码生成算法，如下所示：

4. 迭代生成算法

在(Gray code - Wikipedia)上给了一种以迭代的方式生成任意M进制格雷码的算法。老实讲，没有看懂为什么—更确切地说，没搞明白是怎么设计出来。这里姑且也给出它的python代码实现，以后再来慢慢理解。

5. 代码及测试

import sys
import time
import datetime
import math
import random
from   typing import List
# from   queue import Queue
from   collections import deque
import itertools as it
import numpy as np

def baseM_toGray(M: int, N: int):
    dec2grayDict    = dict()
    gray2decDict    = dict()
    dec2grayDict[0] = N*[0]
    gray2decDict[tuple(N*[0])] = 0
    prevGray        = dec2grayDict[0]
    for k in range(1,M**N):
        # print('k = ', k)
        cnt = 0
        while 1:
            # print('cnt = ', cnt)
            curGray = prevGray.copy()
            curGray[N-cnt-1] = (curGray[N-cnt-1] + 1)%M
            if tuple(curGray) not in gray2decDict:
                dec2grayDict[k] = curGray
                gray2decDict[tuple(curGray)] = k
                prevGray = curGray
                break
            else:                
                cnt += 1
    return dec2grayDict, gray2decDict

def baseM_toGray_2(M: int, N: int, value: int) -> List:
    ''' 
    Parameters
    ----------
    M : int. Base        
    N : int. Number of digits
    value : int. Natural decimal value of the input data

    Returns
    -------
    List
        The base-M gray code representation. 
        [0]: The most siginificant digit
        [-1]: The least siginificant digit
    '''
    # Generate the normal base-M representation of value
    baseM = N * [0]
    for i in range(N-1,-1,-1):
        baseM[i] = value % M
        value    = value //M
    
	# Convert the normal baseM number into the Gray code equivalent. 
    # Note that, the loop starts at the most significant digit and goes down.
    gray  = N * [0]
    shift = 0
    i     = 0
    while i <= N-1:
		# The Gray digit gets shifted down by the sum of the higher digits.
        gray[i] = (baseM[i] + shift) % M
        shift   = shift + M - gray[i];	# Subtract from base so shift is positive      
        i       = i + 1
    return gray           

if __name__ == '__main__':                      
    
    print('baseM_toGray...')
    M = 17
    N = 4
    dec2grayDict, gray2decDict = baseM_toGray(M, N)
    print('M = {0}, N = {1}'.format(M,N))
    # for key in dec2grayDict:
        # print('{0}: {1}'.format(key, dec2grayDict[key]))
    # print('gray2decDict = \n', gray2decDict)

    print('baseM_toGray_2...')    
    for k in range(10):
        x = random.randint(0, M**N)
        gray = baseM_toGray_2(M, N, x)
        print('x={0:6d}: x_gray = {1} vs {2}'.format(x, gray, dec2grayDict[x]))

将M， N分别设置为2和4时，得到4位2进制的格雷码如下所示，这个跟上一篇所生成的4位2进制的格雷码是一致。说明m_coding_gray()是一个向下兼容的任意进制格雷码生成函数，上一篇的所有生成方法都是m_coding_gray()的一种特殊情况。

将M， N分别设置为17和4生成4位17进制的格雷码，并对比两种生成算法的结果确认它们是一致的：

baseM_toGray是一次性生成所有的格雷码，而baseM_toGray_2一次只生成一个数的格雷码。两者各有优缺点。baseM_toGray的使用需要消耗大量的内存，但是它具有通用性，可以用于遍历搜索各种不同的格雷码。baseM_toGray_2更适合于实际应用，根据需要而生成，但是它与上一篇的几种二进制格雷码生成方法一样是特定的生成方法，缺乏通用性。

5. 后记

“故事”讲到这里其实还没有完。

以上（包括上一篇）所给出的格雷码都是基于低位优先更新的策略设计出来的格雷码。但是这并不是唯一的方式，接下来我们要讨论以下对于任意N比特的M进制数究竟有多少种格雷码编码方式。