グレイコード
問題設定
このような問題を考えてみる。
あなたの前には
個のスイッチがある。スイッチはONまたはOFFの状態を取る。最初はすべてOFFとなっている。 このスイッチは金庫の鍵となっていて、これらのスイッチがある特定の組み合わせの状態になったときだけ解錠される。
たとえば、(OFF-ON-ON-OFF-ON)のときだけ金庫は開く。それ以外では金庫は閉じている。といった具合である。
しかし、あなたは正解の組み合わせを忘れてしまっている。
金庫を開けるためにあなたはどのように、スイッチの組み合わせを試していくか?
最も素直な解き方は、全探索(ブルートフォース)である。
つまり、スイッチ列の状態を
たとえば、
コード | 2進数 | スイッチの状態 |
---|---|---|
OFF-OFF-OFF | ||
OFF-OFF-ON | ||
OFF-ON-OFF | ||
OFF-ON-ON | ||
ON-OFF-OFF | ||
ON-OFF-ON | ||
ON-ON-OFF | ||
ON-ON-ON |
これは、良い方法であるが、スイッチの切替の回数が少し多いのが難点である。
たとえば、
少し疲れるので、「もっと少なく済ませることはできないだろうか?」というのが今回の問題である。
のとき
最初の
これをすべて調べて、スイッチ回数が最小のパターンを調べるのは大変であるが、
(1) 0,1,2,3
コード | 2進数 | スイッチの状態 | 前回から変化したスイッチの数 |
---|---|---|---|
OFF-OFF | - | ||
OFF-ON | |||
ON-OFF | |||
ON-ON |
スイッチの回数は
(2) 0,1,3,2
コード | 2進数 | スイッチの状態 | 前回から変化したスイッチの数 |
---|---|---|---|
OFF-OFF | - | ||
OFF-ON | |||
ON-ON | |||
ON-OFF |
スイッチの回数は
(3) 0,2,1,3
コード | 2進数 | スイッチの状態 | 前回から変化したスイッチの数 |
---|---|---|---|
OFF-OFF | - | ||
ON-OFF | |||
OFF-ON | |||
ON-ON |
スイッチの回数は
(4) 0,2,3,1
コード | 2進数 | スイッチの状態 | 前回から変化したスイッチの数 |
---|---|---|---|
OFF-OFF | - | ||
ON-OFF | |||
ON-ON | |||
OFF-ON |
スイッチの回数は
(5) 0,3,1,2
コード | 2進数 | スイッチの状態 | 前回から変化したスイッチの数 |
---|---|---|---|
OFF-OFF | - | ||
ON-ON | |||
OFF-ON | |||
ON-OFF |
スイッチの回数は
(6) 0,3,2,1
コード | 2進数 | スイッチの状態 | 前回から変化したスイッチの数 |
---|---|---|---|
OFF-OFF | - | ||
ON-ON | |||
ON-OFF | |||
OFF-ON |
スイッチの回数は
結論
のとき
次に
このグラフの頂点を1回ずつ通る経路を求めると、これが求めたい探索手順となっているので、これを調べる。
本質的に異なる探索手順は図の右側に示した3つの手順だけである。
なお、一般に、グラフの頂点を1回ずつ通る経路はハミルトン路(Hamiltonian path)と呼ばれている。
対称性を考慮すると、このような経路は
一般の
と解釈することができる。
そのうちのなにか一つをアルゴリズム的に構成することはできないだろうか?
具体的な発想としては
色々考えてみると、次のような方法が考えられる。
(1) まず、最上位ビット
の状態で、下位 ビットについて既知の系列を適用する。 (2) 既知の系列の最後まで来たら、最上位ビットだけを
に変更する。 (3) 次に下位
ビットについて、(1)で使用した系列を逆にした系列を適用する。
たとえば、
のとき、 のとき、 のとき、
この系列は無限に作ることができる。
この系列は、一般にグレイコード(Gray code)と呼ばれている有名な系列である。
グレイコードの数
「グレイコード」という言葉は先に示したアルゴリズムで構成される具体的な系列を指すことが多いが、隣り合うビットが1つだけ異なるような性質を持つ系列を一般に指すこともある。
これは、先に示したように、
このグレイコードの数は
のとき、 のとき、
非常に急激に増加する。
この数列は、OEISのA003043にリストされている。