程式員的算法趣題Q47: 格雷碼循環

目錄

1. 問題描述

2. 解題分析

3. 代碼及測試

4. 後記

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)

        上一篇：Q46: 唯一的OX序列

        下一篇：Q48: 翻轉得到交錯排列

        本系列總目錄參見：程式員的算法趣題：詳細分析和Python全解