10250


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 が一般のときも上手い方法があるはずだと思うのですが、  
何かいい考えはございませんでしょうか？）

[code]

    # 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)
    
[/code]

出力結果  
{"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 以下）でも対応させるには、

[code]

    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
    
[/code]

と変更してください。

（追記）  
myoga さんの回答より、  
n = 2 のときのビットシフトと排他論理和  
にあたるものが、  
整数 i に対し、n 進法表示したものと一桁ずらしたものとを  
mod n で引き算したもの  
であることがわかる。  
例えば、k = 3 のときで考える。  
n = 2 のとき

[code]

    110｜
    -11｜0
    101｜
    
[/code]

n = 3 のとき

[code]

    110｜
    -11｜0
    102｜
    
[/code]


CC BY-SA 3.0
2015-05-15T15:46:19.037
10238
2016-01-01T15:13:21.503
2016-01-01T15:13:21.503
5363
5363
question
ruby アルゴリズム
ｎ進グレイコードの出力について


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

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

[code]

    # 整数 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)
    
[/code]


CC BY-SA 3.0
2015-05-16T04:13:29.587
10250
2015-05-16T18:02:31.193
2015-05-16T18:02:31.193
5300
5300
10238
answer