3

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|

1 件の回答 1

2

(編集: n>10 の場合に対応)

説明のために 10 進数で考えます。普通の 10 進表記で、1 増えた時の変化は常に
 [dk … dp+1 dp 9 … 9]
 → [dk … dp+1 (dp+1) 0 … 0], (1≦p<k)
の様に [変化しない部分 変化する部分] の形になっています。しかも 「変化する部分」の数字は全て1ずつ増加(mod n)します。従って、普通のn進表記について 前の桁との差(mod n) を考えれば、毎回1箇所(「変化する部分」の先頭)しか変化しない符号(=グレイコード)になるのではないかと思います。実際、以下のコードで同じ出力結果が得られます。

# 整数 i から n 進 k 桁グレイコードを計算する
def to_gray(n, k, i)
  i.to_s(n).rjust(k+1,'0').split('').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)
  Hash[(0 .. n**k - 1).map{|i| [i.to_s(n), to_gray(n, k, i)]}]
end

p gray_code(2, 3)
p gray_code(3, 3)
2
  • a, a + 1 に対し、前の桁との差(mod n) をとると、「a + 1 になったとき変化した部分の先頭の場所」だけが異なる符号が作れるというわけですね。例) p Hash[(575..576).map{|i| [i.to_s(4), to_gray(4, 5, i)]}]
    – TOM
    Commented 2015年5月16日 10:08
  • そうです。ところで…よく考えたら 変化する部分 の数字が全て一律に 1 ずつ増える事をちゃんと言わないと駄目ですね。一律に増えるからこそ差を取っても変化しないので。追記しました。
    – akinomyoga
    Commented 2015年5月16日 10:24

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。