ब्रुइज़न टोरस
संयुक्त गणित में, एक डी ब्रुइज़न टोरस, जिसका नाम डच गणितज्ञ निकोलस गोवर्ट डी ब्रुइज़न के नाम पर रखा गया है, एक वर्णमाला ( अधिकांशतः केवल 0 और 1) से प्रतीकों की एक सरणी है जिसमें दिए गए आयाम m × n के हर संभावित आव्यूह को एक बार में सम्मिलित किया जाता है। यह एक टोरस है क्योंकि आव्यूह खोजने के उद्देश्य से किनारों को रैपराउंड माना जाता है। इसका नाम डी ब्रुइज़न अनुक्रम से आया है, जिसे एक विशेष स्थिति माना जा सकता है जहां n = 1 (एक आयाम)।
n
डी ब्रुइज़न टोरी के संबंध में मुख्य विवर्त प्रश्नों में से एक यह है कि क्या किसी विशेष वर्णमाला आकार के लिए डी ब्रुइज़न टोरस का निर्माण किसी दिए गए m और n के लिए किया जा सकता है। यह ज्ञात है कि ये सदैव तब उपस्थित होते हैं जब n = 1 होता है, तब से हमें बस डी ब्रुइज़न अनुक्रम मिलते हैं, जो सदैव उपस्थित रहते हैं। यह भी ज्ञात है कि "वर्ग" टोरी तब उपस्थित होती है जब m = n और सम (विषम स्थिति के लिए परिणामी टोरी वर्गाकार नहीं हो सकती)।[1][2][3]
सबसे छोटा संभव बाइनरी "स्क्वायर" डी ब्रुइज़न टोरस, ऊपर दाईं ओर दर्शाया गया है, जिसे (4,4;2,2)2 डी ब्रुइज़न टोरस (या बस B2) के रूप में दर्शाया गया है, इसमें सभी 2×2 बाइनरी आव्यूह सम्मिलित हैं।
B2
"अनुवाद", "व्युत्क्रम " (0s और 1s का आदान-प्रदान) और "घूर्णन " (90 डिग्री तक) के अतिरिक्त , कोई अन्य (4,4;2,2)2 डी ब्रुइज़न टोरी संभव नहीं है - यह सभी 216 बाइनरी आव्यूह (या 0s और 1s की समान संख्या जैसे उपसमुच्चय पूर्ति बाधाओं) के पूर्ण निरीक्षण द्वारा दिखाया जा सकता है।[4]
n−1 पंक्तियों और स्तंभों को दोहराकर टोरस को अनियंत्रित किया जा सकता है। बिना रैपराउंड के सभी n×n सबमैट्रिस, जैसे कि एक छायांकित पीला, फिर पूरा समुच्चय बनाते हैं:
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
बड़ा उदाहरण: B4
_2_de_Bruijn_torus.svg)
ग्रिड 4×4 आव्यूह में से कुछ को हाइलाइट करता है, जिसमें ऊपरी मार्जिन पर शून्य आव्यूह और आव्यूह सम्मिलित हैं।
अगले संभावित बाइनरी स्क्वायर डी ब्रुइज़न टोरस का एक उदाहरण, (256,256;4,4)2 (संक्षिप्त रूप में B4), स्पष्ट रूप से निर्मित किया गया है।[5]
जिस पेपर में (256,256;4,4)2 डी ब्रुइजन टोरस का एक उदाहरण बनाया गया था, उसमें कम फ़ॉन्ट आकार के अतिरिक्त , बाइनरी के 10 से अधिक पृष्ठ सम्मिलित थे, जिसमें सरणी की प्रति पंक्ति तीन पंक्तियों की आवश्यकता होती थी।
बड़े आकार की बाइनरी डी ब्रुइज़न टोरी
जिस पेपर में (256,256;4,4)2 डी ब्रुइजन टोरस का एक उदाहरण बनाया गया था, उसमें कम फ़ॉन्ट आकार के अतिरिक्त , बाइनरी के 10 से अधिक पृष्ठ सम्मिलित थे, जिसमें सरणी की प्रति पंक्ति तीन पंक्तियों की आवश्यकता होती थी।
बाद में संभावित बाइनरी डी ब्रुइज़न टोरस, जिसमें सभी बाइनरी सम्मिलित हैं 6×6 मैट्रिसेस, होगा 236 = 68,719,476,736 प्रविष्टियाँ, आयाम की एक वर्गाकार सरणी उत्पन्न करती हैं 262,144×262,144, निरूपित ए (262144,262144;6,6)2 डी ब्रुइज़न टोरस या बस B6. इसे सरलता से कंप्यूटर पर संग्रहीत किया जा सकता है - यदि 0.1 मिमी किनारे के पिक्सेल के साथ मुद्रित किया जाता है, तो ऐसे आव्यूह को लगभग 26×26 वर्ग मीटर के क्षेत्र की आवश्यकता होगी।
वस्तु B8, जिसमें सभी बाइनरी 8×8 आव्यूह सम्मिलित हैं और (4294967296,4294967296;8,8)2 दर्शाया गया है, में कुल 264 ≈ 18.447×1018 प्रविष्टियाँ हैं: ऐसे आव्यूह को संग्रहीत करने के लिए 18.5 एक्साबिट्स, या 2.3 एक्साबाइट स्टोरेज की आवश्यकता होगी। उपरोक्त मापदंड पर, यह 429×429 वर्ग किलोमीटर को कवर करेगा।
निम्न तालिका सुपर-घातीय वृद्धि को दर्शाती है।
| n | कोशिकाओं में
सबमैट्रिक्स = n2 |
2n2 की संख्या
उपमैट्रिस |
Bn पक्ष
लंबाई = 2(n2/2) |
|---|---|---|---|
| 2 | 4 | 16 | 4 |
| 4 | 16 | 65 536 | 256 |
| 6 | 36 | 68 719 476 736 | 262 144 |
| 8 | 64 | ~1.84×1019 | ~4.29×109 |
| 10 | 100 | ~1.27×1030 | ~1.13×1015 |
| 12 | 144 | ~2.23×1043 | ~4.72×1021 |
| 14 | 196 | ~1.00×1059 | ~3.17×1029 |
| 16 | 256 | ~1.16×1077 | ~3.40×1038 |
| 18 | 324 | ~3.42×1097 | ~5.85×1048 |
| 20 | 400 | ~2.60×10120 | ~1.61×1060 |
यह भी देखें
- डी ब्रुइन अनुक्रम
- डी ब्रुइन ग्राफ
संदर्भ
- ↑ Fan, C. T.; Fan, S. M.; Ma, S. L.; Siu, M. K. (1985). "On de Bruijn arrays". Ars Combinatoria A. 19: 205–213.
- ↑ Chung, F.; Diaconis, P.; Graham, R. (1992). "Universal cycles for combinatorial structures". Discrete Mathematics. 110 (1): 43–59. doi:10.1016/0012-365x(92)90699-g.
- ↑ Jackson, Brad; Stevens, Brett; Hurlbert, Glenn (Sep 2009). "ग्रे कोड और सार्वभौमिक चक्रों पर अनुसंधान समस्याएं". Discrete Mathematics. 309 (17): 5341–5348. doi:10.1016/j.disc.2009.04.002.
- ↑ Eggen, Bernd R. (1990). "The Binatorix B2". Private communication.
- ↑ Shiu, Wai-Chee (1997). "Decoding de Bruijn arrays constructed by the FFMS method". Ars Combinatoria. 47 (17): 33–48.
