सुपरपरम्यूटेशन: Difference between revisions

From Vigyanwiki
(Created page with "{{short description|String in combinatorial math}} File:Superpermutation distribution.png|thumb|3 प्रतीक सुपरपरमुटेशन में क्र...")
 
No edit summary
Line 1: Line 1:
{{short description|String in combinatorial math}}
{{short description|String in combinatorial math}}
[[File:Superpermutation distribution.png|thumb|3 प्रतीक सुपरपरमुटेशन में क्रमचय का वितरण।]][[साहचर्य]] गणित में, ''एन'' प्रतीकों पर एक सुपरपरमुटेशन एक [[ स्ट्रिंग (कंप्यूटर विज्ञान) ]] है जिसमें एक [[सबस्ट्रिंग]] के रूप में ''एन'' प्रतीकों के प्रत्येक क्रमचय शामिल हैं। जबकि [[तुच्छता (गणित)]] सुपरपरमुटेशन बस एक साथ सूचीबद्ध प्रत्येक क्रमचय से बना जा सकता है, सुपरपरमुटेशन भी छोटा हो सकता है ('n'' = 1 के तुच्छ मामले को छोड़कर) क्योंकि ओवरलैप की अनुमति है। उदाहरण के लिए, ''n'' = 2 के मामले में, सुपरपरमुटेशन 1221 में सभी संभावित क्रम[[परिवर्तन]] (12 और 21) शामिल हैं, लेकिन छोटी स्ट्रिंग 121 में भी दोनों क्रमपरिवर्तन शामिल हैं।
[[File:Superpermutation distribution.png|thumb|3 प्रतीक सुपरपरमुटेशन में क्रमचय का वितरण।]]कॉम्बिनेटरियल गणित में, 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 लंबाई वाले कई सबसे छोटे सुपरपरम्यूटेशन हैं। ऐसा एक सुपरपरम्यूटेशन है नीचे दिखाया गया है, जबकि स्ट्रिंग के दूसरे भाग में (बोल्ड '2' के बाद) सभी चौकों और पांचों को स्विच करके समान लंबाई का एक और प्राप्त किया जा सकता है:<ref>{{cite journal |first=Nathaniel |last=Johnston |date=July 28, 2013 |arxiv=1303.4150 |title=न्यूनतम सुपरपरमुटेशन की गैर-विशिष्टता|journal=Discrete Mathematics |volume=313 |issue=14 |pages=1553–1557 |doi=10.1016/j.disc.2013.03.024 |bibcode=2013arXiv1303.4150J |url=http://www.njohnston.ca/publications/non-uniqueness-of-minimal-superpermutations/ |accessdate=March 16, 2014 | zbl=1368.05004|s2cid=12018639 }}</ref>
यह दिखाया गया है कि 1 ≤ ''n'' ≤ 5 के लिए, ''n'' प्रतीकों पर सबसे छोटे सुपरपरमुटेशन की लंबाई 1 है! + 2! + … + एन! {{OEIS|A180632}}. पहले चार सबसे छोटे सुपरपरम्यूटेशन की लंबाई 1, 3, 9 और 33 है, जिससे स्ट्रिंग्स 1, 121, 123121321, और 123412314231243121342132413214321 बनते हैं। हालाँकि, n = 5 के लिए, 153 लंबाई वाले कई सबसे छोटे सुपरपरम्यूटेशन हैं। ऐसा एक सुपरपरम्यूटेशन है नीचे दिखाया गया है, जबकि स्ट्रिंग के दूसरे भाग में (बोल्ड '2' के बाद) सभी चौकों और पांचों को स्विच करके समान लंबाई का एक और प्राप्त किया जा सकता है:<ref>{{cite journal |first=Nathaniel |last=Johnston |date=July 28, 2013 |arxiv=1303.4150 |title=न्यूनतम सुपरपरमुटेशन की गैर-विशिष्टता|journal=Discrete Mathematics |volume=313 |issue=14 |pages=1553–1557 |doi=10.1016/j.disc.2013.03.024 |bibcode=2013arXiv1303.4150J |url=http://www.njohnston.ca/publications/non-uniqueness-of-minimal-superpermutations/ |accessdate=March 16, 2014 | zbl=1368.05004|s2cid=12018639 }}</ref>123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321
123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321


'एन''> 5 के मामलों के लिए, सबसे छोटा सुपरपरमुटेशन अभी तक सिद्ध नहीं हुआ है और न ही उन्हें खोजने के लिए कोई पैटर्न है, लेकिन उनके लिए निचली और ऊपरी सीमा पाई गई है।
'एन''> 5 के मामलों के लिए, सबसे छोटा सुपरपरमुटेशन अभी तक सिद्ध नहीं हुआ है और न ही उन्हें खोजने के लिए कोई पैटर्न है, लेकिन उनके लिए निचली और ऊपरी सीमा पाई गई है।

Revision as of 12:30, 31 March 2023

3 प्रतीक सुपरपरमुटेशन में क्रमचय का वितरण।

कॉम्बिनेटरियल गणित में, n प्रतीकों पर एक सुपरपरम्यूटेशन एक स्ट्रिंग है जिसमें एक सबस्ट्रिंग के रूप में n प्रतीकों के प्रत्येक क्रमपरिवर्तन होते हैं। जबकि साधारण सुपरपरमुटेशन को एक साथ सूचीबद्ध प्रत्येक क्रमचय से बनाया जा सकता है, सुपरपरमुटेशन भी छोटा हो सकता है (n = 1 के तुच्छ मामले को छोड़कर) क्योंकि ओवरलैप की अनुमति है। उदाहरण के लिए, n = 2 के मामले में, सुपरपरमुटेशन 1221 में सभी संभावित क्रमपरिवर्तन (12 और 21) सम्मिलित हैं, लेकिन छोटी स्ट्रिंग 121 में भी दोनों क्रमपरिवर्तन सम्मिलित हैं।

यह दिखाया गया है कि 1 ≤ n ≤ 5 के लिए, n प्रतीकों पर सबसे छोटे सुपरपरमुटेशन की लंबाई 1 है! + 2! + … + एन! (sequence A180632 in the OEIS). पहले चार सबसे छोटे सुपरपरम्यूटेशन की लंबाई 1, 3, 9 और 33 है, जिससे स्ट्रिंग्स 1, 121, 123121321, और 123412314231243121342132413214321 बनते हैं। हालाँकि, n = 5 के लिए, 153 लंबाई वाले कई सबसे छोटे सुपरपरम्यूटेशन हैं। ऐसा एक सुपरपरम्यूटेशन है नीचे दिखाया गया है, जबकि स्ट्रिंग के दूसरे भाग में (बोल्ड '2' के बाद) सभी चौकों और पांचों को स्विच करके समान लंबाई का एक और प्राप्त किया जा सकता है:[1]123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321

'एन> 5 के मामलों के लिए, सबसे छोटा सुपरपरमुटेशन अभी तक सिद्ध नहीं हुआ है और न ही उन्हें खोजने के लिए कोई पैटर्न है, लेकिन उनके लिए निचली और ऊपरी सीमा पाई गई है।

सुपरपरमुटेशन ढूँढना

2 प्रतीकों वाले सुपरपरमुटेशन से 3 प्रतीकों के साथ एक सुपरपरमुटेशन के निर्माण का आरेख।

ऑर्डर का सुपरपरमुटेशन बनाने के लिए सबसे आम एल्गोरिदम में से एक एक पुनरावर्ती एल्गोरिथम है। सबसे पहले, आदेश का सुपरपरम्यूटेशन सुपरपरमुटेशन में वे कैसे प्रकट हुए, इसके क्रम में इसके अलग-अलग क्रमपरिवर्तन में विभाजित किया गया है। उनमें से प्रत्येक क्रमचय को तब स्वयं की एक प्रति के साथ रखा जाता है जिसमें दो प्रतियों के बीच एक nth प्रतीक जोड़ा जाता है। अंत में, प्रत्येक परिणामी संरचना को एक दूसरे के बगल में रखा जाता है और सभी आसन्न समान प्रतीकों को मिला दिया जाता है।[2]

उदाहरण के लिए, क्रम 3 का एक सुपरपरमुटेशन 2 प्रतीकों वाले एक से बनाया जा सकता है; सुपरपरमुटेशन 121 से शुरू होकर इसे क्रमचय 12 और 21 में विभाजित करते हुए, क्रमचय को कॉपी किया जाता है और 12312 और 21321 के रूप में रखा जाता है। उन्हें 1231221321 बनाने के लिए एक साथ रखा जाता है, और बीच में समान आसन्न 2s को 123121321 बनाने के लिए विलय कर दिया जाता है, जो वास्तव में क्रम 3 का एक सुपरपरमुटेशन है। यह एल्गोरिद्म 5 से कम या उसके बराबर सभी n के लिए सबसे कम संभव सुपरपरमुटेशन का परिणाम देता है, लेकिन n के आगे बढ़ने पर सबसे कम संभव से अधिक लंबा हो जाता है।[2]

सुपरपरमुटेशन खोजने का एक अन्य तरीका एक ग्राफ (असतत गणित) बनाने में निहित है जहां प्रत्येक क्रमचय एक शीर्ष (ग्राफ सिद्धांत) है और प्रत्येक क्रमचय एक किनारे से जुड़ा हुआ है। प्रत्येक किनारे के साथ एक भार जुड़ा होता है; वज़न की गणना यह देखकर की जाती है कि एक क्रमचय के अंत में कितने वर्ण जोड़े जा सकते हैं (शुरुआत से समान वर्णों को छोड़कर) दूसरे क्रमपरिवर्तन के परिणामस्वरूप।[2]उदाहरण के लिए, 123 से 312 के किनारे का वजन 2 है क्योंकि 123 + 12 = 12312 = 312। बनाए गए ग्राफ के माध्यम से कोई भी हैमिल्टनियन पथ एक सुपरपरमुटेशन है, और सबसे कम वजन वाले पथ को खोजने की समस्या यात्रा विक्रेता का एक रूप बन जाती है। संकट। लंबाई से छोटे सुपरपरमुटेशन का पहला उदाहरण रॉबिन ह्यूस्टन द्वारा इस पद्धति पर एक कंप्यूटर खोज का उपयोग करते हुए पाया गया।

निचली सीमा, या हारुही समस्या

सितंबर 2011 में, 4chan के विज्ञान और गणित (/sci/) इंटरनेट मंचों पर एक गुमनाम पोस्टर ने साबित किया कि n प्रतीकों (n ≥ 2) पर सबसे छोटा सुपरपरमुटेशन कम से कम लंबाई n है! + (एन−1)! + (एन−2)! + एन - 3।[3]जापानी एनिमे े श्रृंखला हारुही सुजुमिया के संदर्भ में, समस्या को द हारुही प्रॉब्लम के रूप में इमेजबोर्ड पर प्रस्तुत किया गया था:[4] यदि आप श्रृंखला के पहले सीज़न के 14 एपिसोड हर संभव क्रम में देखना चाहते हैं, तो आपको एपिसोड की सबसे छोटी कड़ी क्या देखनी होगी?[5] इस निचली सीमा का प्रमाण अक्टूबर 2018 में गणितज्ञ और कंप्यूटर वैज्ञानिक रॉबिन ह्यूस्टन द्वारा इसके बारे में ट्वीट किए जाने के बाद आम जनता के हित में आया।[3] 25 अक्टूबर 2018 को, रॉबिन ह्यूस्टन, जे पैनटोन, और विंस वैटर ने इस प्रमाण का एक परिष्कृत संस्करण इंटेगर सीक्वेंस (OEIS) के ऑन-लाइन एनसाइक्लोपीडिया में पोस्ट किया।[5][6] इस प्रमाण का एक प्रकाशित संस्करण, जिसका श्रेय बेनामी 4चान पोस्टर को दिया गया है, में दिखाई देता है Engen and Vatter (2019).[7] हारुही समस्या के लिए विशेष रूप से (14 प्रतीकों के मामले में), वर्तमान निचली और ऊपरी सीमा क्रमशः 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.


संदर्भ

  1. ↑ 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. ↑ 2.0 2.1 2.2 2.3 2.4 2.5 Egan, Greg (20 October 2018). "सुपरपरम्यूटेशन". gregegan.net. Retrieved 15 January 2020.
  3. ↑ 3.0 3.1 3.2 Griggs, Mary Beth. "An anonymous 4chan post could help solve a 25-year-old math mystery". The Verge.
  4. ↑ Anon, - San (September 17, 2011). "Permutations Thread III ニア愛". Warosu.{{cite web}}: CS1 maint: url-status (link)
  5. ↑ 5.0 5.1 Klarreich, Erica (November 5, 2018). "विज्ञान कथा लेखक ग्रेग एगन और बेनामी मठ विशेषज्ञ अग्रिम क्रमचय समस्या". Quanta Magazine (in English). Retrieved June 21, 2020.{{cite web}}: CS1 maint: url-status (link)
  6. ↑ Anonymous 4chan poster; Houston, Robin; Pantone, Jay; Vatter, Vince (October 25, 2018). "सबसे छोटे सुपरपैटर्न की लंबाई पर एक निचली सीमा" (PDF). OEIS. Retrieved 27 October 2018.
  7. ↑ Engen, Michael; Vatter, Vincent (2021), "Containing all permutations", American Mathematical Monthly, 128 (1): 4–24, doi:10.1080/00029890.2021.1835384
  8. ↑ 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].


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=सुपरपरम्यूटेशन&oldid=141381’