デ・ブリュイン・トーラス

組合せ数学において、オランダの数学者ニコラス・ゴーバート・デ・ブリュインにちなんで名付けられたデ・ブリュイン・トーラスは、アルファベット（多くの場合は0と1のみ）の記号の配列であり、与えられた次元m × nのすべての可能な行列を1回だけ含みます。行列を見つける目的で辺がラップアラウンドと見なされるため、トーラスと呼ばれます。その名前は、 n = 1（1次元） の特別なケースと見なすことができるデ・ブリュイン列に由来しています。

デ・ブリュイン・トーラスに関する未解決の主な疑問の 1 つは、特定のアルファベット サイズのデ・ブリュイン・トーラスが、与えられたmとnに対して構築できるかどうかです。これらはn = 1 のときに常に存在することが知られています。これは、常に存在するデ・ブリュイン数列が得られるからです。また、 m = nで偶数の場合は常に「正方形」トーラスが存在することも知られています(奇数の場合は、結果として得られるトーラスは正方形にはなりません)。^{[1] [2] [3]}

右上に描かれている、(4,4;2,2) ₂ド ブリュイン トーラス (または単にB ₂ ) として表される、可能な限り最小のバイナリ「正方形」ド ブリュイン トーラスには、すべての2×2バイナリ マトリックスが含まれます。

「平行移動」、「反転」（0と1の交換）、「回転」（90度）以外には、他の（4,4;2,2）₂ ^{de Bruijnトーラスは不可能である。これは、2 16}のバイナリ行列（または0と1の数が等しいなどの制約を満たすサブセット）をすべて完全に検査することで示されます。^[4]

トーラスはn −1 行と列を繰り返すことで展開できます。黄色で塗りつぶされた部分行列など、ラップアラウンドのない すべてのn × n部分行列は、完全なセットを形成します。

次に可能性のある2元「正方形」のデ・ブリュイン・トーラスの例である(256,256;4,4) ₂（略してB4）が明示的に構築されている。_[ ^5]

右側の画像は、(256,256;4,4) ₂ de Bruijn トーラス/配列の例を示しています。ここでは、ゼロは白のピクセルとして、1 は赤のピクセルとしてそれぞれエンコードされています。

(256,256;4,4) ₂ de Bruijn トーラスの例が構築された論文には、フォント サイズが縮小されているにもかかわらず、配列の行ごとに 3 行必要となる 10 ページを超えるバイナリが含まれていました。

2 進6×6行列をすべて含む、可能な 2 進 de Bruijn トーラスは、2 ³⁶ = 68,719,476,736 個のエントリを持ち、次元262,144×262,144の正方配列を生成し、(262144,262144;6,6) ₂ de Bruijn トーラスまたは単にB _{6と表記されます。これはコンピューターに簡単に保存できます。0.1 mm 辺のピクセルで印刷する場合、このような行列には約 26×26}平方メートルの面積が必要です。

すべてのバイナリ8×8行列を含み、 (4294967296,4294967296;8,8) ₂と表記されるオブジェクトB ₈には、合計2 ⁶⁴ ≈ 18.447×10 ^{18のエントリがあります。このような行列を保存するには、18.5 エクサビット、つまり2.3}エクサバイトのストレージが必要です。上記のスケールでは、429×429平方キロメートルをカバーします。

次の表は超指数関数的成長を示しています。

デ・ブリュイントーラスは、例えば、光学的な地面パターンに基づいた カメラ^[6] 、ロボット^[7]、または実体^{[8]の位置特定などの空間符号化のコンテキストで使用されます。}

これらは、チェス盤のキャリブレーションパターンに位置エンコーディングを追加する光学カメラキャリブレーションターゲットであるPuzzleBoard ^{[9]の基礎としても使用されています。 [10]}

デ・ブリュイン・トーラスは、アノトシステムと同様にデジタルペーパーの実装に使用できます。ただし、アノトセルにはデ・ブリュイン・トーラスの2つの状態ではなく、4つの状態があります。また、異なるオフセットを持つ6ビットのデ・ブリュインシーケンスを列として使用します。^[11]

• デジタルペーパー
• デ・ブリュインシーケンス
• デ・ブリュイングラフ
• チェス盤検出

• シンボルのすべての部分配列の組み合わせを含む最小配列: De Bruijn シーケンスとトーラス