再帰を使ってグレイコードを生成するPythonプログラムの書き方

グレイコード（Gray Code）とは、隣り合う数値同士でビットが必ず1つだけしか変化しない特別な二進数表記のことです。デジタル回路設計やエラー検出、位置センサーなど、さまざまな分野で活用されています。

Pythonで再帰的な考え方を利用してグレイコードを生成するには、まず空のリストを作成し、初期値として「0」と「1」を追加するメソッドを定義します。その後、関数内で複数の「for」ループを組み合わせることで、指定した桁数分のグレイコードを効率よく生成できます。

サンプルコード

import math as mt
def generate_gray_list(my_val):
    if (my_val <= 0):
        return
    my_list = list()
    my_list.append("0")
    my_list.append("1")
    i = 2
    j = 0
    while(True):
        if i >= 1 << my_val:
            break
        for j in range(i - 1, -1, -1):
            my_list.append(my_list[j])
        for j in range(i):
            my_list[j] = "0" + my_list[j]
        for j in range(i, 2 * i):
            my_list[j] = "1" + my_list[j]
        i = i << 1
    for i in range(len(my_list)):
        print(my_list[i])
my_num = 3
print("The number is :")
print(my_num)
print("Method to convert gray code to binary is being called...")
generate_gray_list(my_num)

出力結果

The number is :
3
Method to convert gray code to binary is being called...
000
001
011
010
110
111
101
100

処理の流れと解説

• まず、必要なパッケージをインポートします。

• 空のリストを作成するメソッド generate_gray_list を定義します。引数が0以下の場合は何もせずに終了します。

• 作成したリストに対して、初期値である「0」と「1」を追加します。

• 複数の「for」ループを使い、既存の要素を逆順にコピーしながら反復処理を行います。これにより、鏡像となるパターンが生成されます。

• 前半の要素には先頭に「0」を、後半の要素には先頭に「1」を付加することで、新しい桁のグレイコードを作り出します。

• イテレータに対して左シフト演算子（<<）を適用し、その結果を目標のビット数と比較することで、whileループの継続条件を判定しています。

• メソッドの外部からは、生成したいビット数（ここでは3）を引数として渡して呼び出します。

• 最終的に、生成されたすべてのグレイコードがコンソールに出力されます。

このように、リストの鏡像コピーとプレフィックス（接頭辞）の付加を繰り返すシンプルな手法により、任意のビット数のグレイコードを短いコードで生成することが可能です。