Torus De Bruijna

STL torusa de Bruijna

(16,32;3,3) 2

z jedynkami jako panelami i 0 jako dziurami w siatce – przy stałej orientacji każda macierz

3\times3 pojawia się dokładnie raz

W matematyce kombinatorycznej torus De Bruijna , nazwany na cześć holenderskiego matematyka Nicolaasa Goverta de Bruijna , to tablica symboli z alfabetu (często tylko 0 i 1), która zawiera każdą możliwą macierz o danych wymiarach $m \times n$ dokładnie raz. Jest to torus , ponieważ krawędzie są uważane za zawijane w celu znalezienia macierzy. Jego nazwa pochodzi od ciągu De Bruijna , który można uznać za szczególny przypadek, gdy $n = 1$ (jeden wymiar).

$m$ i $n$ można skonstruować torus De Bruijna dla określonego rozmiaru alfabetu . Wiadomo, że te istnieją zawsze, gdy $n = 1$ , ponieważ wtedy po prostu otrzymujemy ciągi De Bruijna, które zawsze istnieją. Wiadomo również, że torus „kwadratowy” istnieje zawsze, gdy $m = n$ i parzysta (w nieparzystym przypadku wynikowy torus nie może być kwadratowy).

Najmniejszy możliwy binarny „kwadratowy” torus de Bruijna, przedstawiony powyżej po prawej stronie, oznaczony jako $(4,4;2,2) 2$ torus de Bruijna (lub po prostu jako $B 2$ ), zawiera wszystkie macierze binarne $2\times2 .$

B2 _{_}

(4,4;2,2) torus de Bruijna. Każda macierz binarna 2 na 2 może zostać znaleziona w niej dokładnie raz.

Poza „translacją”, „inwersją” (zamiana 0 i 1) i „obrótem” (o 90 stopni) żadne inne ( $4,4;2,2) 2$ de Bruijn tori nie są możliwe – można to wykazać przez pełną kontrolę wszystkich 2 ¹⁶ macierzy binarnych (lub podzbiór spełniający ograniczenia, takie jak równa liczba zer i jedynek).

Torus De Bruijna (8,8; 3,2) zawierający wszystkie 64 możliwe macierze 3-rzędowe × 2-kolumnowe dokładnie raz, z zawijaniem - dolna połowa jest negatywem górnej połowy

Torus można rozwinąć, powtarzając n −1 wierszy i kolumn. Wszystkie n × n bez zawijania, takie jak ta zacieniona na żółto, tworzą następnie kompletny zestaw:

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

Większy przykład: B ₄

B ₄ jako binarna macierz kwadratowa Siatka wyróżnia niektóre macierze 4×4, w tym macierze zer i jedynek na górnym marginesie.

Przykład następnego możliwego binarnego „kwadratu” torusa de Bruijna, $(256,256;4,4) 2$ (w skrócie B ₄ ), został wyraźnie skonstruowany.

Obraz po prawej pokazuje przykład torusa / tablicy $(256,256;4,4) 2 de Bruijn, gdzie zera zostały zakodowane odpowiednio jako białe, a jedynki jako czerwone piksele.$

Binarny tori de Bruijn o większym rozmiarze

Artykuł, w którym skonstruowano przykład torusa $(256,256;4,4) 2$ de Bruijn, zawierał ponad 10 stron binarnych, pomimo zmniejszonego rozmiaru czcionki, wymagającego trzech wierszy na rząd tablicy.

Kolejny możliwy binarny torus de Bruijna, zawierający wszystkie binarne macierze $6 \times 6$ , miałby $236 = 68 719 476$ 736 wpisów, dając kwadratową tablicę o wymiarze $262 144 \times 262 144$ , oznaczoną jako $(262144,262144;6,6) 2$ torus de Bruijna lub po prostu B6 _. Można to łatwo zapisać na komputerze - w przypadku wydrukowania pikseli o boku 0,1 mm taka matryca wymagałaby powierzchni około 26 × 26 metrów kwadratowych .

Obiekt B ₈ , zawierający wszystkie binarne macierze $8\times8$ i oznaczony $(4294967296,4294967296;8,8) 2$ , ma łącznie 2 ⁶⁴ ≈ 18,447×10 ¹⁸ wpisów: przechowywanie takiej macierzy wymagałoby 18,5 eksabitów, czyli 2,3 eksabajtów składowy. W powyższej skali obejmowałby 429 × 429 kilometrów kwadratowych .

Poniższa tabela ilustruje superwykładniczy wzrost.

N	Komórki w podmacierzy = n ²	Liczba podmacierzy = 2 ^{n ²}	B _n długość boku = 2 ^{( n ² /2)}
2	4	16	4
4	16	65 536	256
6	36	68 719 476 736	262 144
8	64	~1,84 × 10 ¹⁹	~4,29 × 10 ⁹
10	100	~1,27 × 10 ³⁰	~1,13 × 10 ¹⁵
12	144	~2,23 × 10 ⁴³	~4,72 × 10 ²¹
14	196	~1,00 × 10 ⁵⁹	~3,17 × 10 ²⁹
16	256	~1,16 × 10 ⁷⁷	~3,40 × 10 ³⁸
18	324	~3,42 × 10 ⁹⁷	~5,85 × 10 ⁴⁸
20	400	~2,60 × 10 ¹²⁰	~1,61 × 10 ⁶⁰

Zobacz też

Linki zewnętrzne

Minimalne tablice zawierające wszystkie kombinacje symboli podtablic: sekwencje De Bruijna i torusy