程序员的算法趣题Q47: 格雷码循环

1. 问题描述

2. 解题分析

这道题目的焦点是任意M进制数的格雷码的生成。这个确实是有难度的问题，因为它已经不是常规的算法设计问题。要求对格雷码的生成算法有了解，尤其是针对任意M进制的格雷码的生成并不是一般的二进制格雷码的生成算法的简单推广。

以本问题为契机我特意调查了一下二进制格雷码以及任意M进制格雷码的生成算法。详情参见从二进制格雷码到任意进制格雷码(1)(2)

我自己基于格雷码的定义给出的基于深度优先搜索的任意M进制格雷码的生成算法由于（是预先一次性生成N位M进制的所有格雷码码字）需要巨量的存储，因此并不适用于作为本题的解决方案。对于M=16，N=6的情况，总共有M**N=16**6=2**24~~10**9，这个存储量有点惊人。

原书中给出一个提示，基于二进制格雷码生成的异或转换算法的扩展得出任意M进制格雷码生成算法。。。真的有醍醐灌顶之感！

另外，在https://en.wikipedia.org/wiki/Gray_code中给出了一种基于迭代的方式生成M进制格雷码的算法。本文先基于这种算法给出题解。关于任意M进制格雷码生成的“异或转换”算法后面再来补充。

M进制格雷码的详细迭代生成算法这里不再解释（事实是我没有看懂这个算法是怎么设计出来的，因此无法解释，感兴趣的伙伴自己就着代码慢慢品味吧）。

整体的算法流程如下：

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Thu Oct  7 10:31:11 2021

@author: chenxy
"""

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, 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      

def cyclicSteps(M: int, N: int, start: int)->int:
    
    cur = start
    step  = 0
    while 1:
        step = step + 1
        curGray = baseM_toGray(M,N,cur)
        # print(curGray)
    
        # Take curGray as normal baseM representation and calulate its value
        cur   = 0
        scale = 1        
        for k in range(N-1,-1,-1):            
            cur = cur + curGray[k] * scale
            scale = scale * M
        if cur == start:
            break
    return step
        
if __name__ == '__main__':           
    
    M = 16
    N = 6
    start = 0x808080
    step  = cyclicSteps(M,N,start)
    print('start = 0x{0:6x}, step = {1}'.format(start,step))
    start = 0xABCDEF
    step  = cyclicSteps(M,N,start)
    print('start = 0x{0:6x}, step = {1}'.format(start,step))

运行结果：

start = 0x808080, step = 8

start = 0xabcdef, step = 64

4. 后记

关于格雷码生成的更多参见：

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

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