De Bruijn torus
Inom kombinatorisk matematik är en De Bruijn torus , uppkallad efter den holländska matematikern Nicolaas Govert de Bruijn , en samling symboler från ett alfabet (ofta bara 0 och 1) som innehåller varje möjlig matris med givna dimensioner m × n exakt en gång. Det är en torus eftersom kanterna anses omslutande i syfte att hitta matriser. Dess namn kommer från De Bruijn-sekvensen , som kan betraktas som ett specialfall där n = 1 (en dimension).
En av de viktigaste öppna frågorna angående De Bruijn tori är om en De Bruijn torus för en viss alfabetsstorlek kan konstrueras för en given m och n . Det är känt att dessa alltid existerar när n = 1 , sedan får vi helt enkelt De Bruijn-sekvenserna, som alltid finns. Det är också känt att "fyrkantiga" tori existerar när m = n och jämn (för det udda fallet kan den resulterande tori inte vara kvadratisk).
Den minsta möjliga binära "kvadrat" de Bruijn torus, avbildad ovan till höger, betecknad som (4,4;2,2) 2 de Bruijn torus (eller helt enkelt som B 2 ), innehåller alla 2×2 binära matriser.
B 2
Förutom "översättning", "inversion" (byte av 0:or och 1:or) och "rotation" (med 90 grader), är inga andra ( 4,4;2,2) 2 de Bruijn tori möjliga – detta kan visas genom fullständig inspektion av alla 2 16 binära matriser (eller delmängd som uppfyller begränsningar som lika många nollor och enor).
Torus kan rullas ut genom att upprepa n −1 rader och kolumner. Alla n × n submatriser utan omslutning, till exempel den gula, bildar sedan hela uppsättningen:
1 0 1 1 1 1 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 1 1 1
Större exempel: B 4
_2_de_Bruijn_torus.svg)
B 4 som en binär kvadratisk matris Rutnätet framhäver några av 4×4-matriserna, inklusive de med nollor och ettor i den övre marginalen.
Ett exempel på nästa möjliga binära "kvadrat" de Bruijn torus, (256,256;4,4) 2 (förkortat som B 4 ), har konstruerats explicit.
Bilden till höger visar ett exempel på en (256,256;4,4) 2 de Bruijn torus/array, där nollorna har kodats som vita respektive de som röda pixlar.
Binary de Bruijn tori av större storlek
Papperet där ett exempel på (256,256;4,4) 2 de Bruijn-torus konstruerades innehöll över 10 sidor binär, trots dess minskade teckenstorlek, som krävde tre rader per rad av array.
Den efterföljande möjliga binära de Bruijn torusen, som innehåller alla binära 6×6 -matriser, skulle ha 2 36 = 68 719 476 736 poster, vilket ger en kvadratisk matris med dimensionen (262144 till 262 144×262 144 , betecknad en ellerijnrus) 42626; helt enkelt B 6 . Detta kan lätt lagras på en dator – om det skrivs ut med pixlar på sidan 0,1 mm skulle en sådan matris kräva en yta på cirka 26×26 kvadratmeter .
Objektet B 8 , som innehåller alla binära 8×8 -matriser och betecknat (4294967296,4294967296;8,8) 2 , har totalt 2 64 ≈ 18.447×10 18 poster: att lagra en sådan matris skulle kräva 18,5 bytes exabitar eller 2 exabitar av lagring. På ovanstående skala skulle den täcka 429×429 kvadratkilometer .
Följande tabell illustrerar den superexponentiella tillväxten.
| n |
Celler i en submatris = n 2 |
Antal submatriser = 2 n 2 |
B n sidolängd = 2 ( n 2 /2 ) |
|---|---|---|---|
| 2 | 4 | 16 | 4 |
| 4 | 16 | 65 536 | 256 |
| 6 | 36 | 68 719 476 736 | 262 144 |
| 8 | 64 | ~1,84 × 10 19 | ~4,29 × 10 9 |
| 10 | 100 | ~1,27 × 10 30 | ~1,13 × 10 15 |
| 12 | 144 | ~2,23 × 10 43 | ~4,72 × 10 21 |
| 14 | 196 | ~1,00 × 10 59 | ~3,17 × 10 29 |
| 16 | 256 | ~1,16 × 10 77 | ~3,40 × 10 38 |
| 18 | 324 | ~3,42 × 10 97 | ~5,85 × 10 48 |
| 20 | 400 | ~2,60 × 10 120 | ~1,61 × 10 60 |