Gray Code - n-bit巡回Gray符号列生成

標準Gray code公式 G(i) = i ^ (i >> 1) による最適化実装

概要

問題：n-bitのGray code列（長さ2n）を生成。隣接する整数のバイナリ表現が1 bitだけ異なり、先頭（0）と末尾も1 bit差（巡回性）を満たす。

要件

  • すべての整数は [0, 2n - 1] の範囲
  • 先頭は 0
  • 重複なし
  • 隣接する整数が1 bitだけ異なる（巡回含む）

解法：標準Gray code公式 G(i) = i ^ (i >> 1) を i=0..2n-1 に適用。Pythonのリスト内包表記で一括構築し、O(2n)時間・O(1)追加メモリを実現。

ステップバイステップ解説

Step 1: 初期化

入力 n から列長 M = 2n を計算

Step 2: インデックス走査

range(0, M) の各 i に対してループ開始

Step 3: 右シフト

i を1ビット右シフト（i >> 1）

Step 4: XOR演算

i と (i >> 1) のXORを計算：G(i) = i ^ (i >> 1)

Step 5: リスト追加

G(i) を結果リストに追加

Step 6: 完了

全インデックス処理後、Gray code列を返却

n = 3 M = 2^3 = 8 初期化: シーケンス長を計算 ループ: i = 0 から 7 i = 0 i = 1 i = 2 ... i = 7 全てのインデックスで反復 右シフト (i >> 1) i = 5 (101) i >> 1 = 2 (010) ビットを右に1つシフト XOR演算 i = 5 (101) ⊕ 2 (010) G(5) = 7 (111) XOR: i ^ (i >> 1) 結果に追加 result = [0, 1, 3, 2, 6, ...] G(5) = 7 result = [0, 1, 3, 2, 6, 7, ...] 完成したGray Codeシーケンス n = 3: [0, 1, 3, 2, 6, 7, 5, 4] (000, 001, 011, 010, 110, 111, 101, 100) ✓ 隣接要素は1ビットだけ異なる 完成したシーケンスを返す

Python実装（LeetCode形式） 

from __future__ import annotations

from typing import List


class Solution:
    """
    Gray Code generator (n-bit).

    Generates a valid n-bit Gray code sequence using the standard formula:
    G(i) = i XOR (i >> 1)
    """

    def grayCode(self, n: int) -> List[int]:
        """
        Return any valid n-bit Gray code sequence.

        Args:
            n: Number of bits (1 <= n <= 16)

        Returns:
            List of 2^n integers forming a valid Gray code sequence

        Time Complexity: O(2^n)
        Space Complexity: O(2^n) for output, O(1) additional

        Example:
            >>> Solution().grayCode(2)
            [0, 1, 3, 2]  # Binary: [00, 01, 11, 10]
        """
        # Step 1: Compute sequence length (2^n)
        m: int = 1 << n

        # Step 2-5: Apply Gray code formula to all indices
        # List comprehension is fastest in CPython (C-level range + bulk allocation)
        # G(i) = i XOR (i >> 1) guarantees adjacent 1-bit difference
        result: List[int] = [i ^ (i >> 1) for i in range(m)]

        # Step 6: Return completed sequence
        return result


# Example usage and verification
if __name__ == "__main__":
    sol = Solution()

    # Example 1: n=2
    print(sol.grayCode(2))  # [0, 1, 3, 2]

    # Example 2: n=3
    print(sol.grayCode(3))  # [0, 1, 3, 2, 6, 7, 5, 4]

    # Verify adjacent 1-bit difference
    def verify_gray_code(code: List[int]) -> bool:
        n = len(code)
        for i in range(n):
            diff = code[i] ^ code[(i + 1) % n]
            if bin(diff).count('1') != 1:
                return False
        return True

    print(verify_gray_code(sol.grayCode(3)))  # True

視覚的図解

アルゴリズムフロー

開始: 入力 n M = 2^n を計算 (1 << n) i を 0 から M-1 まで 各インデックスでループ G(i) = i ^ (i >> 1) XOR演算で右シフト G(i) を結果に追加 ループ

説明：入力 n から M=2n を計算し、0からM-1まで各インデックス i に対して Gray code 公式 i ^ (i >> 1) を適用。結果をリストに追加して返却。

例：n=3 のGray Code生成過程

i (dec) i (bin) i >> 1 (bin) G(i) = i ^ (i >> 1) G(i) (dec)
0 000 000 000 0
1 001 000 001 1
2 010 001 011 3
3 011 001 010 2
4 100 010 110 6
5 101 010 111 7
6 110 011 101 5
7 111 011 100 4

結果：[0, 1, 3, 2, 6, 7, 5, 4]
各隣接ペア（0→1, 1→3, ..., 4→0）は1 bitだけ異なる。

計算量

時間計算量

O(2n)

M = 2n 個の要素を1回走査。各インデックスで定数時間のビット演算（右シフト＋XOR）のみ。

空間計算量

O(2n)

出力リスト（長さ2n）が必要。追加メモリはO(1)（インデックス変数のみ）。

アルゴリズム比較

アプローチ 時間 空間（追加） 実装難易度 備考
公式法（本実装） O(2n) O(1) 低 最速・最小メモリ
反射法（鏡映） O(2n) O(2n) 中 段階的構築、教育的
DFSバックトラック O(2n·n) O(2n) 高 実用性低（遅い）

最適化ポイント：Pythonのリスト内包表記は CPython の C 実装を直接利用するため、明示的 for ループより高速。ビット演算（左シフト、右シフト、XOR）は CPU 命令に直接マップされる最速演算。