सुपरपरम्यूटेशन
संयोजी गणित में, n प्रतीकों पर अति-क्रमचय एक स्ट्रिंग है जिसमें एक सबस्ट्रिंग के रूप में n प्रतीकों के प्रत्येक क्रमपरिवर्तन होते हैं। जबकि साधारण अति-क्रमचय को एक साथ सूचीबद्ध करके प्रत्येक क्रमचय को बनाया जा सकता है, अति-क्रमचय छोटा भी हो सकता है n = 1 के तुच्छ स्तिथियों को छोड़कर ,क्योंकि अतिव्यापन की अनुमति होता है। उदाहरण के लिए, n = 2 के विषय में, अति-क्रमचय 1221 में सभी संभावित क्रमपरिवर्तन (12 और 21) सम्मिलित हैं, परंतु छोटी स्ट्रिंग 121 में भी दोनों क्रमपरिवर्तन सम्मिलित हैं।
यह दिखाया गया है कि 1 ≤ n ≤ 5 के लिए, n प्रतीकों पर सबसे छोटे अति-क्रमचय की लंबाई 1 है! + 2! + … + एन! (OEIS में अनुक्रम A180632)है । पहले चार सबसे छोटे अति-क्रमचय की लंबाई 1, 3, 9, और 33 है, जिससे स्ट्रिंग्स 1, 121, 123121321, और 123412314231243121342132413214321 निर्मित होते हैं। यद्यपि, n = 5 के लिए, 153 की लंबाई वाले कई छोटे अति-क्रमचय हैं। ऐसा एक अति-क्रमचय नीचे दिखाया गया है, जबकि स्ट्रिंग के दूसरे भाग में सभी चौकों और पांचों को स्विच करके समान लंबाई का एक और स्ट्रिंग प्राप्त किया जा सकता है।:[1]123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321
'n > 5, के विषयो के लिए, सबसे छोटा अति-क्रमचय अभी तक सिद्ध नहीं हुआ है और न ही उन्हें खोजने के लिए कोई पैटर्न है, लेकिन उनके लिए निचली और ऊपरी सीमा पाई गई है।
अति-क्रमचय ढूँढना
क्रम n का अति-क्रमचय बनाने के लिए सबसे सरल प्रारूप में से एक पुनरावर्ती प्रारूप है। पहले, क्रम अति-क्रमचय को, इसके अलग-अलग क्रमपरिवर्तन में विभाजित करके देखा जाता है कि यह अति-क्रमचय में कैसे दिखाई देता है। उनमें से प्रत्येक क्रमचय को तब स्वयं की एक प्रति के साथ रखा जाता है जिसमें दो प्रतियों के बीच एक nth प्रतीक जोड़ा जाता है। अंत में, प्रत्येक परिणामी संरचना को एक दूसरे के बगल में रखा जाता है और सभी आसन्न समान प्रतीकों को मिला दिया जाता है।[2]
उदाहरण के लिए, क्रम 3 का एक अति-क्रमचय 2 प्रतीकों वाले एक से बनाया जा सकता है; अति-क्रमचय 121 से प्रारंभ होकर इसे क्रमचय 12 और 21 में विभाजित करते हुए, क्रमचय को कॉपी किया जाता है और 12312 और 21321 के रूप में रखा जाता है। उन्हें 1231221321 बनाने के लिए एक साथ रखा जाता है, और बीच में समान आसन्न 2s को 123121321 बनाने के लिए विलय कर दिया जाता है, जो वास्तव में क्रम 3 का एक अति-क्रमचय है। यह प्रारूप 5 से कम या उसके बराबर सभी n के लिए सबसे कम संभव अति-क्रमचय का परिणाम देता है, लेकिन n के आगे बढ़ने पर सबसे कम संभव से अधिक लंबा हो जाता है।[2]
अति-क्रमचय खोजने का एक अन्य तरीका एक ग्राफ असतत गणित बनाने में निहित है जहां प्रत्येक क्रमचय एक शीर्ष ग्राफ सिद्धांत है और प्रत्येक क्रमचय एक किनारे से जुड़ा हुआ है। प्रत्येक किनारे के साथ एक भार जुड़ा होता है; वज़न की गणना यह देखकर की जाती है कि एक क्रमचय के अंत में कितने वर्ण जोड़े जा सकते हैं दूसरे क्रमपरिवर्तन के परिणामस्वरूप।,123 से 312 के किनारे का वजन 2 है क्योंकि 123 + 12 = 12312 = 312 बनाए गए ग्राफ के माध्यम से कोई भी हैमिल्टनियन पथ एक अति-क्रमचय है, और सबसे कम वजन वाले पथ को खोजने की समस्या यात्रा विक्रेता का एक रूप बन जाती है। लंबाई से छोटे अति-क्रमचय का पहला उदाहरण रॉबिन ह्यूस्टन द्वारा इस पद्धति पर एक कंप्यूटर खोज का उपयोग करते हुए पाया गया।
निचली सीमा, या हारुही समस्या
सितंबर 2011 में, 4चान के विज्ञान और गणित इंटरनेट मंचों पर एक गुमनाम पोस्टर ने साबित किया कि n प्रतीकों (n ≥ 2) पर सबसे छोटा अति-क्रमचय कम से कम लंबाई n है! + (एन−1)! + (एन−2)! + एन - 3 है ।[3]जापानी एनिमेए श्रृंखला हारुही सुजुमिया के संदर्भ में, समस्या को द हारुही प्रॉब्लम के रूप में इमेजबोर्ड पर प्रस्तुत किया गया था:[4] यदि आप श्रृंखला के पहले सीज़न के 14 एपिसोड हर संभव क्रम में देखना चाहते हैं, तो आपको एपिसोड की सबसे छोटी कड़ी क्या देखनी होगी?[5] इस निचली सीमा का प्रमाण अक्टूबर 2018 में गणितज्ञ और कंप्यूटर वैज्ञानिक रॉबिन ह्यूस्टन द्वारा इसके बारे में ट्वीट किए जाने के बाद आम जनता के हित में आया।[3] 25 अक्टूबर 2018 को, रॉबिन ह्यूस्टन, जे पैनटोन, और विंस वैटर ने इस प्रमाण का एक परिष्कृत संस्करण इंटेगर सीक्वेंस (ओईआईएस) के ऑन-लाइन एनसाइक्लोपीडिया में पोस्ट किया।[5][6] इस प्रमाण का एक प्रकाशित संस्करण, जिसका श्रेय बेनामी 4चान पोस्टर को दिया गया है, में दिखाई देता है एंगेन और वैटर.2019[7]हारुही समस्या के लिए विशेष रूप से वर्तमान निचली और ऊपरी सीमा क्रमशः 93,884,313,611 और 93,924,230,411 है।[3]इसका मतलब है कि श्रृंखला को हर संभव क्रम में देखने में लगभग 4 मिलियन वर्ष लगेंगे।
ऊपरी सीमा
20 अक्टूबर 2018 को, सममित समूह के केली ग्राफ के माध्यम से हैमिल्टनियन पथ के निर्माण के लिए हारून विलियम्स द्वारा एक निर्माण को अपनाने से,[8] साइंस फिक्शन लेखक और गणितज्ञ ग्रेग एगन ने लंबाई एन के अति-क्रमचय का उत्पादन करने के लिए एक प्रारूप तैयार किया! + (एन−1)! + (एन−2)! + (एन−3)! + एन - 3।[2]2018 तक, ये n ≥ 7 के लिए जाने जाने वाले सबसे छोटे अति-क्रमचय थे।यद्यपि,1 फरवरी 2019 को, बोगडान कोंडा ने घोषणा की कि उन्होंने लंबाई 5907, या (n! + (n−1)! + (n−2)! + (n−3)! + n − 3) − 1, जो एक नया रिकॉर्ड था।[2]27 फरवरी 2019 को, रॉबिन ह्यूस्टन द्वारा विकसित विचारों का उपयोग करते हुए, ईगन ने लंबाई 5906 के n = 7 के लिए एक अति-क्रमचय का उत्पादन किया।[2]क्या n> 7 के मानों के लिए समान छोटे अति-क्रमचय भी उपलब्ध हैं, यह एक खुला प्रश्न है। n = 7 के लिए वर्तमान सर्वोत्तम निचली सीमाअभी भी 5884 है।
यह भी देखें
- सुपरपैटर्न, एक क्रमचय जिसमें क्रमचय पैटर्न के रूप में n प्रतीकों का प्रत्येक क्रमचय सम्मिलित है।
- डी ब्रुजन अनुक्रम, चक्रीय अनुक्रमों के साथ एक समान समस्या है।
अग्रिम पठन
- Ashlock, Daniel A.; Tillotson, Jenett (1993), "Construction of small superpermutations and minimal injective superstrings", Congressus Numerantium, 93: 91–98, Zbl 0801.05004
- Anonymous 4chan Poster; Houston, Robin; Pantone, Jay; Vatter, Vince (October 25, 2018). "A lower bound on the length of the shortest superpattern" (PDF). On-Line Encyclopedia of Integer Sequences.
संदर्भ
- ↑ Johnston, Nathaniel (July 28, 2013). "न्यूनतम सुपरपरमुटेशन की गैर-विशिष्टता". Discrete Mathematics. 313 (14): 1553–1557. arXiv:1303.4150. Bibcode:2013arXiv1303.4150J. doi:10.1016/j.disc.2013.03.024. S2CID 12018639. Zbl 1368.05004. Retrieved March 16, 2014.
- ↑ 2.0 2.1 2.2 2.3 2.4 Egan, Greg (20 October 2018). "सुपरपरम्यूटेशन". gregegan.net. Retrieved 15 January 2020.
- ↑ 3.0 3.1 3.2 Griggs, Mary Beth. "An anonymous 4chan post could help solve a 25-year-old math mystery". The Verge.
- ↑ Anon, - San (September 17, 2011). "Permutations Thread III ニア愛". Warosu.
{{cite web}}: CS1 maint: url-status (link) - ↑ 5.0 5.1 Klarreich, Erica (November 5, 2018). "विज्ञान कथा लेखक ग्रेग एगन और बेनामी मठ विशेषज्ञ अग्रिम क्रमचय समस्या". Quanta Magazine (in English). Retrieved June 21, 2020.
{{cite web}}: CS1 maint: url-status (link) - ↑ Anonymous 4chan poster; Houston, Robin; Pantone, Jay; Vatter, Vince (October 25, 2018). "सबसे छोटे सुपरपैटर्न की लंबाई पर एक निचली सीमा" (PDF). OEIS. Retrieved 27 October 2018.
- ↑ Engen, Michael; Vatter, Vincent (2021), "Containing all permutations", American Mathematical Monthly, 128 (1): 4–24, doi:10.1080/00029890.2021.1835384
- ↑ Aaron, Williams (2013). "Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2)". arXiv:1307.2549v3 [math.CO].
बाहरी संबंध
- The Minimal Superpermutation Problem - Nathaniel Johnston's blog
- Grime, James. "Superpermutations - Numberphile" (video). YouTube. Brady Haran. Retrieved 1 February 2018.
- The 4chan post on /sci/, archived on warosu.org
- Tweet by Robin Houston, which brought attention to the 4chan post
