kビットのn進グレイコード(http://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%AC%E3%82%A4%E3%82%B3%E3%83%BC%E3%83%89)
を出力するコードを書いてみたのですが、
もっと簡単に書くにはどのようにすればよろしいでしょうか?
(n = 2 のとき、ビットシフトと排他論理和のループで書けるので、
n が一般のときも上手い方法があるはずだと思うのですが、
何かいい考えはございませんでしょうか?)
# n <= 10
def gray_code(n, k)
ary = Array.new(k, 0)
hash = {0.to_s(n) => ary.join}
(1..n ** k - 1).each{|i|
j = k - 1
ary[j] = (ary[j] + 1) % n
while hash.value?(ary.join)
ary[j] = (ary[j] - 1) % n
j -= 1
ary[j] = (ary[j] + 1) % n
end
hash[i.to_s(n)] = ary.join
}
hash
end
p gray_code(2, 3)
p gray_code(3, 3)
出力結果
{"0"=>"000", "1"=>"001", "10"=>"011", "11"=>"010", "100"=>"110", "101"=>"111", "110"=>"101", "111"=>"100"}
{"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"}
なお、n > 10 (ただし、n は 36 以下)でも対応させるには、
def gray_code(n, k)
ary = Array.new(k, '0')
hash = {0.to_s(n) => ary.join}
(1..n ** k - 1).each{|i|
j = k - 1
ary[j] = ((ary[j].to_i(n) + 1) % n).to_s(n)
while hash.value?(ary.join)
ary[j] = ((ary[j].to_i(n) - 1) % n).to_s(n)
j -= 1
ary[j] = ((ary[j].to_i(n) + 1) % n).to_s(n)
end
hash[i.to_s(n)] = ary.join
}
hash
end
と変更してください。
(追記)
myoga さんの回答より、
n = 2 のときのビットシフトと排他論理和
にあたるものが、
整数 i に対し、n 進法表示したものと一桁ずらしたものとを
mod n で引き算したもの
であることがわかる。
例えば、k = 3 のときで考える。
n = 2 のとき
110|
-11|0
101|
n = 3 のとき
110|
-11|0
102|