グレイコード

グレイコードの出力 - みずぴー日記にインスパイヤされてグレイコードを出力してみます。 グレイコードはグレイコード - Wikipedia にも書かれていますが、今回はGray code - Wikipedia, the free encyclopedia にある n 桁 (n ビット) のグレイコードを生成します。

上記の URL を見れば分かるように、折り返しを使って先頭に 0 か 1 を付け加えるだけで簡単にグレイコードを生成することができます。 また、再帰的に呼び出すことでコードも短縮することができます。

#! /usr/local/bin/nawk -f
# gray_code.awk
# n 桁のグレイコードの出力
# usage: nawk -f gray_code.awk [num]

BEGIN {
    num = ARGV[1] ? ARGV[1] : 3;

    print gray_code("0,1", num);
}

# gray_code():  num 桁のグレイコード
#   in:     gray コードの初期値 (gray)
#           整数 (num)
#   out:    num 桁のグレイコードの羅列 (カンマ区切り)
function gray_code(gray, num) {
    num_gray = split(gray, arr_gray, ",");

    if (length(arr_gray[1]) == num) {
        return gray;
    }

    new_gray = "";

    for (i = 1; i <= num_gray; i++) {
        new_gray = new_gray ",0" arr_gray[i];
    }

    for (i = num_gray; i >= 1; i--) {
        new_gray = new_gray ",1" arr_gray[i];
    }

    sub(/^,/, "", new_gray);

    return gray_code(new_gray, num);
}

引数に桁数を与えて実行します。

$ nawk -f gray_code.awk 2 | sed 's|,|\n|g'
00
01
11
10

$ nawk -f gray_code.awk 5 | sed 's|,|\n|g'
00000
00001
00011
00010
00110
00111
00101
00100
01100
01101
01111
01110
01010
01011
01001
01000
11000
11001
11011
11010
11110
11111
11101
11100
10100
10101
10111
10110
10010
10011
10001
10000

ここでは awk で処理しやすいように、カンマ区切りで出力し、それを sed で改行にしてみました。