ゆえあって n進グレイコードへの変換式を作ることになった。
グレイコード - Wikipedia
グレイコードについてはここにあるとおりである。2進グレイコードなら、ネットを検索すればたくさん出てくる。具体例は、Ruby のハッシュで表すとこんな感じだ。
{"0"=>"000", "1"=>"001", "10"=>"011", "11"=>"010",
"100"=>"110", "101"=>"111", "110"=>"101", "111"=>"100"}キーが 2進数、値が 2進グレイコードである。10進数の 3 から 4 は 2進数だと 011 から 100 で、3つのビットが変化している。しかし、グレイコードだと 010 から 110 で 1つのビットしか変化していない。このように、連続する数値ならすべてのビットの変化が 1となるのがグレイコードである。
2進数から 2進グレイコードへの変換は、Wikipedia にあるとおりだ。
「対象の二進表現」と、「それを１ビット右シフトし、先頭に０をつけたもの」との排他的論理和をとる。
C言語なら v ^ (v >> 1) と表現されるとあるとおりである。ちなみにこれは Ruby コードでもまったく同じ表現になる。
n進グレイコードでも同じ筈である。連続するグレイコードはすべての桁の変化を合わせても 1しか変っていない、そういう数になるはずである。しかしこの変換式を作ろうとしても、自分にはむずかしかった。で、ネットに頼ったところ、Ruby で既にすばらしいコードが！ なんと実質 1行である。これ以上のコードは書けないので素直にコピペさせてもらいます。
#整数 i から n進 k桁グレイコードを計算する def to_gray(n, k, i) i.to_s(n).rjust(k + 1, "0").chars.each_cons(2) .map {|d| ((d[1].to_i(n) - d[0].to_i(n)) % n).to_s(n)}.join end #n進 k桁グレイコード表を作る def gray_code(n, k) (0..n ** k - 1).map {|i| [i.to_s(n), to_gray(n, k, i)]}.to_h end p gray_code(3, 3)
なお、Ruby なので n は 36 まで可能である。
実行結果。3進グレイコードへの変換である。（3進なので、0 と 2 の差は 1 であることに注意されたい。）
{"0"=>"000", "1"=>"001", "2"=>"002", "10"=>"012", "11"=>"010",
"12"=>"011", "20"=>"021", "21"=>"022", "22"=>"020", "100"=>"120",
"101"=>"121", "102"=>"122", "110"=>"102", "111"=>"100",
"112"=>"101", "120"=>"111", "121"=>"112", "122"=>"110",
"200"=>"210", "201"=>"211", "202"=>"212", "210"=>"222",
"211"=>"220", "212"=>"221", "220"=>"201", "221"=>"202", "222"=>"200"}コピペ元はここ。
考察もすばらしいので、是非よく読んで頂きたい。
逆変換は一応自分で考えてみた。こんな感じにできた。
def gray_to_num(g, n) s = g[0] g.chars.map {|x| x.to_i(n)}.inject {|h, x| s += (h = (h + x) % n).to_s(n); h} s end
しかしこれも、関連記事の方にもっといいコードがあった。
def to_n_ary(n, str) a = 0 str.chars.map{|d| ((a += d.to_i(n)) % n).to_s(n)}.join end
美しい。
グレイコードとは何やら数学的な遊びで、実用的な価値はなさそうに思えるかも知れないが、そうでもないようだ。例えば思考実験として、こんな場合が考えられる。情報の通信過程で、ある種のノイズが入り得るとする。それは、情報のどこかに 1ビットが挿入されるというものだ。例えば 2進数 0100 に 1ビットのノイズが入り、1100 になったとする。これを 10進数に直すと 4 から 12 で、伝達される値が大きく変ってしまうことになる。しかし 2進グレイコードなら 0100 から 1100 は 10進数で 7 から 8 の変化に過ぎず、10進数でも値は 1 しかちがわない。よってノイズの影響が少ない可能性がある（0000 から 1000 へのような場合はさすがにダメだが）。このような場合である。
