グレイコード

問題設定

このような問題を考えてみる。

あなたの前には$n$個のスイッチがある。スイッチはONまたはOFFの状態を取る。最初はすべてOFFとなっている。

このスイッチは金庫の鍵となっていて、これらのスイッチがある特定の組み合わせの状態になったときだけ解錠される。

たとえば、(OFF-ON-ON-OFF-ON)のときだけ金庫は開く。それ以外では金庫は閉じている。といった具合である。

しかし、あなたは正解の組み合わせを忘れてしまっている。

金庫を開けるためにあなたはどのように、スイッチの組み合わせを試していくか？

最も素直な解き方は、全探索(ブルートフォース)である。

つまり、スイッチ列の状態を$2^n$の数値にコーディングし、$0$から$2^n-1$までのスイッチの状態を試していくことである。

たとえば、$n=3$の場合、次のように試していくことになる。

これは、良い方法であるが、スイッチの切替の回数が少し多いのが難点である。

たとえば、$0$ -> $1$の切り替えは右のスイッチを押すだけでよいが、$1$ -> $2$の切り替えでは真ん中と右のスイッチを押さなければならない。 この方法では、スイッチを押す回数は全部で$11$回となる。

少し疲れるので、「もっと少なく済ませることはできないだろうか？」というのが今回の問題である。

$n=2$のとき

最初の$0$は固定するとして、残りの$2^n-1$の数値を並べる方法は$(2^n-1)!$通りある。

これをすべて調べて、スイッチ回数が最小のパターンを調べるのは大変であるが、$n=2$の時なら6通りに過ぎないので、すべてを調べることができる。

(1) 0,1,2,3

スイッチの回数は$4$回である。

(2) 0,1,3,2

スイッチの回数は$3$回である。

(3) 0,2,1,3

スイッチの回数は$4$回である。

(4) 0,2,3,1

スイッチの回数は$3$回である。

(5) 0,3,1,2

スイッチの回数は$5$回である。

(6) 0,3,2,1

スイッチの回数は$5$回である。

結論

$n=2$の場合、$\{00,01,11,10\}$もしくは$\{00,10,11,01\}$が最小の探索手順である。

$n=3$のとき

次に$n=3$のときを考える。今度は全部調べると$7!=5040$通りであって大変なので、最初から最小手数$7$回を目標にする。

$0$から$2^n-1$までの各数値を頂点として、「ビットが1つだけ異なる」という関係を持つ頂点を結ぶと、次の図の左のような立方体のグラフが得られる。

このグラフの頂点を1回ずつ通る経路を求めると、これが求めたい探索手順となっているので、これを調べる。

本質的に異なる探索手順は図の右側に示した3つの手順だけである。

なお、一般に、グラフの頂点を1回ずつ通る経路はハミルトン路(Hamiltonian path)と呼ばれている。

対称性を考慮すると、このような経路は$000$スタートのものに限っても$3\cdot 3\cdot 2=18$個ある (最初の行き先の頂点の選び方で$3$通り、次の行き先の頂点の選び方で$2$通りある)。

一般の$n$

$n=3$のときの考え方によると、この問題は

$n$次元超立方体グラフ(hypercube graph)のある頂点を出発点とするハミルトン路を求める問題

と解釈することができる。$n=2$で$2$通り、$n=3$で$18$通りであるから、こういったハミルトン路はかなりありそうである。

そのうちのなにか一つをアルゴリズム的に構成することはできないだろうか?

具体的な発想としては$n-1$次元超立方体グラフのハミルトン路がわかっているのであれば、それを利用して$n$次元超立方体のハミルトン路を構成することはできないだろうか。

色々考えてみると、次のような方法が考えられる。

(1) まず、最上位ビット$0$の状態で、下位$n-1$ビットについて既知の系列を適用する。

(2) 既知の系列の最後まで来たら、最上位ビットだけを$1$に変更する。

(3) 次に下位$n-1$ビットについて、(1)で使用した系列を逆にした系列を適用する。

たとえば、$n=1$のときの系列$\{0,1\}$を出発点として、$n=2,3,4$について、このアルゴリズムで構成される系列は次のようなものである。

• $n=2$のとき、$\{00,01,11,10\}$
• $n=3$のとき、$\{000,001,011,010,110,111,101,100\}$
• $n=4$のとき、$\{0000,0001,0011,0010,0110,0111,0101,0100,1100,1101,1111,1110,1010,1011,1001,1000\}$

この系列は無限に作ることができる。

この系列は、一般にグレイコード(Gray code)と呼ばれている有名な系列である。

グレイコードの数

「グレイコード」という言葉は先に示したアルゴリズムで構成される具体的な系列を指すことが多いが、隣り合うビットが1つだけ異なるような性質を持つ系列を一般に指すこともある。

これは、先に示したように、 $n$次元超立方体グラフ(hypercube graph)のある頂点を出発点とするハミルトン路と同一視できるものである。

このグレイコードの数は$n=1$のときは$1$つ、$n=2$のときは$2$つ、$n=3$のときは$18$個まで求めたが、この後どのように増えるかというと次のようになる。

• $n=4$のとき、$5,712$
• $n=5$のとき、$5,859,364,320$

非常に急激に増加する。

この数列は、OEISのA003043にリストされている。