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

From Vigyanwiki
No edit summary
No edit summary
 
(16 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{short description|String in combinatorial math}}
{{short description|String in combinatorial math}}संयोजी गणित में, n प्रतीकों पर एक सुपरपरम्यूटेशन एक शृंखला  है जिसमें एक उपशृंखला के रूप में n प्रतीकों के प्रत्येक क्रमपरिवर्तन होते हैं। जबकि साधारण सुपरपरमुटेशन को एक साथ जोड़े गए प्रत्येक क्रमपरिवर्तन से बनाया जा सकता है, सुपरपरमुटेशन भी छोटा हो सकता है (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 की लंबाई वाले कई छोटे सुपरपरमुटेशन हैं। ऐसा एक सुपरपरमुटेशन नीचे दिखाया गया है, जबकि स्ट्रिंग के दूसरे भाग में सभी चौकों और पांचों को स्विच करके समान लंबाई का एक और स्ट्रिंग प्राप्त किया जा सकता है।:<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
यह दिखाया गया है कि 1 ≤ n ≤ 5 के लिए, n प्रतीकों पर सबसे छोटे सुपरपरमुटेशन की लंबाई है 1! + 2! + … + ''n''! ओईआईएस में अनुक्रम A180632 है। पहले चार सबसे छोटे सुपरपरम्यूटेशन की लंबाई 1, 3, 9 और 33 होती है, जिससे शृंखला 1, 121, 123121321, और 123412314231243121342132413214321 बनते हैं। यद्यपि, n = 5 के लिए, 153 की लंबाई वाले कई छोटे सुपरपरमुटेशन होता हैं। ऐसा एक सुपरपरमुटेशन नीचे दिखाया गया है, जबकि शृंखला के दूसरे भाग में सभी चौथे और पांचवे को स्विचन करके समान लंबाई का एक और शृंखला प्राप्त किया जा सकता है।


'''n'' > 5, ''के विषयो के लिए, सबसे छोटा सुपरपरमुटेशन अभी तक सिद्ध नहीं हुआ है और न ही उन्हें खोजने के लिए कोई पैटर्न है, लेकिन उनके लिए निचली और ऊपरी सीमा पाई गई है।''
<nowiki>:</nowiki><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>1234512341523412534123541231452314253142351423154231245312435124315243125431'''2'''13452134251342153421354213
 
n > 5 केस्थिति के लिए, सबसे छोटा सुपरपरमुटेशन अभी तक सिद्ध नहीं हुआ है और न ही उन्हें खोजने के लिए कोई पैटर्न है, लेकिन उनके लिए निचली और ऊपरी सीमाएं पाई गई हैं


== सुपरपरमुटेशन ढूँढना ==
== सुपरपरमुटेशन ढूँढना ==
[[file:superpermutations.jpg|thumb|2 प्रतीकों वाले सुपरपरमुटेशन से 3 प्रतीकों के साथ एक सुपरपरमुटेशन के निर्माण का आरेख।]]ऑर्डर का सुपरपरमुटेशन बनाने के लिए सबसे आम प्रारूप में से एक n एक पुनरावर्ती प्रारूप है। सबसे पहले, आदेश का सुपरपरम्यूटेशन <math>n-1</math> सुपरपरमुटेशन में वे कैसे दिखाई दिए, इसके क्रम में इसके अलग-अलग क्रमपरिवर्तन में विभाजित किया गया है। उनमें से प्रत्येक क्रमचय को तब स्वयं की एक प्रति के साथ रखा जाता है जिसमें दो प्रतियों के बीच एक nth प्रतीक जोड़ा जाता है। अंत में, प्रत्येक परिणामी संरचना को एक दूसरे के बगल में रखा जाता है और सभी आसन्न समान प्रतीकों को मिला दिया जाता है।<ref name="Greg Egan">{{cite web|url=http://www.gregegan.net/SCIENCE/सुपरपरम्यूटेशन/सुपरपरम्यूटेशन.html|title=सुपरपरम्यूटेशन|last=Egan|first=Greg|date=20 October 2018|website=gregegan.net|access-date=15 January 2020}}</ref>
[[file:superpermutations.jpg|thumb|2 प्रतीकों वाले सुपरपरमुटेशन से 3 प्रतीकों के साथ एक सुपरपरमुटेशन के निर्माण का आरेख।]]क्रम n का सुपरपरमुटेशन बनाने के लिए सबसे सरल कलन विधियो में से एक पुनरावर्ती कलन विधि है। पहले, क्रम <math>n-1</math> सुपरपरमुटेशन को,अलग-अलग क्रमपरिवर्तन में विभाजित करके देखा जाता है कि यह सुपरपरमुटेशन में कैसे दिखाई देता है। उनमें से प्रत्येक क्रमचय को तब स्वयं की एक प्रति के साथ रखा जाता है जिसमें दो प्रतियों के मध्य एक nth प्रतीक जोड़ा जाता है। अंत में, प्रत्येक परिणामी संरचना को एक दूसरे के बगल में रखा जाता है और सभी आसन्न समान प्रतीकों को मिला दिया जाता है।<ref name="Greg Egan">{{cite web|url=http://www.gregegan.net/SCIENCE/सुपरपरम्यूटेशन/सुपरपरम्यूटेशन.html|title=सुपरपरम्यूटेशन|last=Egan|first=Greg|date=20 October 2018|website=gregegan.net|access-date=15 January 2020}}</ref>
उदाहरण के लिए, क्रम 3 का एक सुपरपरमुटेशन 2 प्रतीकों वाले एक से बनाया जा सकता है; सुपरपरमुटेशन 121 से प्रारंभ होकर इसे क्रमचय 12 और 21 में विभाजित करते हुए, क्रमचय को कॉपी किया जाता है और 12312 और 21321 के रूप में रखा जाता है। उन्हें 1231221321 बनाने के लिए एक साथ रखा जाता है, और बीच में समान आसन्न 2s को 123121321 बनाने के लिए विलय कर दिया जाता है, जो वास्तव में क्रम 3 का एक सुपरपरमुटेशन है। यह प्रारूप 5 से कम या उसके बराबर सभी n के लिए सबसे कम संभव सुपरपरमुटेशन का परिणाम देता है, लेकिन n के आगे बढ़ने पर सबसे कम संभव से अधिक लंबा हो जाता है।<ref name="Greg Egan"/>
उदाहरण के लिए, क्रम 3 का एक सुपरपरमुटेशन 2 प्रतीकों वाले से एक बनाया जा सकता है; सुपरपरमुटेशन 121 से प्रारंभ होकर इसे क्रमचय 12 और 21 में विभाजित करते हुए, क्रमचय को कॉपी किया जाता है और 12312 और 21321 के रूप में रखा जाता है। उन्हें 1231221321 बनाने के लिए एक साथ रखा जाता है, और मध्य में समान आसन्न 2s को 123121321 बनाने के लिए विलय कर दिया जाता है, जो वास्तव में क्रम 3 का एक सुपरपरमुटेशन है। यह कलन विधि 5 से कम या 5 के बराबर सभी n के लिए सबसे कम संभव सुपरपरम्यूटेशन का परिणाम देता है, लेकिन सबसे कम संभव से अधिक लंबा हो जाता है क्योंकि n इससे आगे बढ़ जाता है


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


=== निचली सीमा, या हारुही समस्या ===
=== निचली सीमा, या हारुही समस्या ===
सितंबर 2011 में, [[4chan|4चान]] के विज्ञान और गणित इंटरनेट मंचों पर एक गुमनाम पोस्टर ने साबित किया कि n प्रतीकों (n ≥ 2) पर सबसे छोटा सुपरपरमुटेशन कम से कम लंबाई n है! + (एन−1)! + (एन−2)! + एन - 3 है ।<ref name=":0" />जापानी [[ एनिमे |एनिमेए]] श्रृंखला [[हारुही सुजुमिया]] के संदर्भ में, समस्या को द हारुही प्रॉब्लम के रूप में इमेजबोर्ड पर प्रस्तुत किया गया था:<ref>{{Cite web |last=Anon |first=- San |date=September 17, 2011 |title=Permutations Thread III  ニア愛 |url=https://warosu.org/sci/thread/S3751105#p3751197 |url-status=live |website=Warosu}}</ref> यदि आप श्रृंखला के पहले सीज़न के 14 एपिसोड हर संभव क्रम में देखना चाहते हैं, तो आपको एपिसोड की सबसे छोटी कड़ी क्या देखनी होगी?<ref name=":1">{{Cite web|last=Klarreich|first=Erica|date=November 5, 2018|title=विज्ञान कथा लेखक ग्रेग एगन और बेनामी मठ विशेषज्ञ अग्रिम क्रमचय समस्या|url=https://www.quantamagazine.org/sci-fi-writer-greg-egan-and-anonymous-math-whiz-advance-permutation-problem-20181105/|url-status=live|archive-url=|archive-date=|access-date=June 21, 2020|website=[[Quanta Magazine]]|language=en}}</ref> इस निचली सीमा का प्रमाण अक्टूबर 2018 में गणितज्ञ और कंप्यूटर वैज्ञानिक रॉबिन ह्यूस्टन द्वारा इसके बारे में ट्वीट किए जाने के बाद आम जनता के हित में आया।<ref name=":0">{{cite web |last1=Griggs |first1=Mary Beth |title=An anonymous 4chan post could help solve a 25-year-old math mystery |url=https://www.theverge.com/2018/10/24/18019464/4chan-anon-anime-haruhi-math-mystery |website=The Verge}}</ref> 25 अक्टूबर 2018 को, रॉबिन ह्यूस्टन, जे पैनटोन, और विंस वैटर ने इस प्रमाण का एक परिष्कृत संस्करण इंटेगर सीक्वेंस (ओईआईएस) के ऑन-लाइन एनसाइक्लोपीडिया में पोस्ट किया।<ref name=":1" /><ref>{{cite web|url=https://oeis.org/A180632/a180632.pdf|title=सबसे छोटे सुपरपैटर्न की लंबाई पर एक निचली सीमा|author1=Anonymous 4chan poster|last2=Houston|first2=Robin|date=October 25, 2018|website=OEIS|accessdate=27 October 2018|last3=Pantone|first3=Jay|last4=Vatter|first4=Vince}}</ref> इस प्रमाण का एक प्रकाशित संस्करण, जिसका श्रेय बेनामी 4चान पोस्टर को दिया गया है, में दिखाई देता है एंगेन और वैटर.2019<ref name="engenvatter">{{citation
सितंबर 2011 में, 4चान के विज्ञान और गणित बोर्ड पर एक अज्ञात पोस्टर ने सिद्ध कर दिया कि n प्रतीकों (n ≥ 2) पर सबसे छोटा सुपरपरमुटेशन कम से कम लंबाई ''n''! + (''n''−1)! + (''n''−2)! + ''n'' − 3 है।<ref name=":0" />जापानी [[ एनिमे |एनिमेए]] श्रृंखला [[हारुही सुजुमिया]] के संदर्भ में, समस्या को द हारुही प्रॉब्लम के रूप में इमेजबोर्ड पर प्रस्तुत किया गया था:<ref>{{Cite web |last=Anon |first=- San |date=September 17, 2011 |title=Permutations Thread III  ニア愛 |url=https://warosu.org/sci/thread/S3751105#p3751197 |url-status=live |website=Warosu}}</ref> यदि आप श्रृंखला के पहले सीज़न के 14 एपिसोड हर संभव क्रम में देखना चाहते हैं, तो आपको एपिसोड की सबसे छोटी कड़ी क्या देखनी होगी?<ref name=":1">{{Cite web|last=Klarreich|first=Erica|date=November 5, 2018|title=विज्ञान कथा लेखक ग्रेग एगन और बेनामी मठ विशेषज्ञ अग्रिम क्रमचय समस्या|url=https://www.quantamagazine.org/sci-fi-writer-greg-egan-and-anonymous-math-whiz-advance-permutation-problem-20181105/|url-status=live|archive-url=|archive-date=|access-date=June 21, 2020|website=[[Quanta Magazine]]|language=en}}</ref> इस निचली सीमा का प्रमाण अक्टूबर 2018 में आम जनता के हित मे आया जब गणितज्ञ और कंप्यूटर वैज्ञानिक रॉबिन ह्यूस्टन द्वारा इसके बारे में ट्वीट किया ।<ref name=":0">{{cite web |last1=Griggs |first1=Mary Beth |title=An anonymous 4chan post could help solve a 25-year-old math mystery |url=https://www.theverge.com/2018/10/24/18019464/4chan-anon-anime-haruhi-math-mystery |website=The Verge}}</ref> तो 25 अक्टूबर 2018 को, रॉबिन ह्यूस्टन, जे पैनटोन, और विंस वैटर ने इस प्रमाण का एक परिष्कृत संस्करण इंटेगर अनुक्रमों के ऑन-लाइन विश्वकोश (ओईआईएस) में प्रकाशित किया।<ref name=":1" /><ref>{{cite web|url=https://oeis.org/A180632/a180632.pdf|title=सबसे छोटे सुपरपैटर्न की लंबाई पर एक निचली सीमा|author1=Anonymous 4chan poster|last2=Houston|first2=Robin|date=October 25, 2018|website=OEIS|accessdate=27 October 2018|last3=Pantone|first3=Jay|last4=Vatter|first4=Vince}}</ref> इस प्रमाण का एक प्रकाशित संस्करण, लिए एंगेन और वैटर 2019 में दिखाई देता है, जिसका श्रेय अज्ञात 4चान पोस्टर को दिया जाता है, विशेष रूप से "द हारुही प्रॉब्लम" के लिए(14 प्रतीकों के स्थिति)  <ref name="engenvatter">{{citation
| last1 = Engen | first1 = Michael  
| last1 = Engen | first1 = Michael  
| last2 = Vatter | first2 = Vincent
| last2 = Vatter | first2 = Vincent
Line 24: Line 25:
| issue = 1
| issue = 1
| pages = 4–24
| pages = 4–24
}}</ref>हारुही समस्या के लिए विशेष रूप से वर्तमान निचली और ऊपरी सीमा क्रमशः 93,884,313,611 और 93,924,230,411 है।<ref name=":0" />इसका मतलब है कि श्रृंखला को हर संभव क्रम में देखने में लगभग 4 मिलियन वर्ष लगेंगे।
}}</ref>वर्तमान निचली और ऊपरी सीमा क्रमशः 93,884,313,611 और 93,924,230,411 है।।<ref name=":0" />इसका अर्थ है कि श्रृंखला को हर संभव क्रम में देखने में लगभग 4 मिलियन वर्ष लगेंगे।


=== ऊपरी सीमा ===
=== ऊपरी सीमा ===
20 अक्टूबर 2018 को, [[सममित समूह]] के [[केली ग्राफ]] के माध्यम से हैमिल्टनियन पथ के निर्माण के लिए हारून विलियम्स द्वारा एक निर्माण को अपनाने से,<ref>{{Cite arXiv|eprint=1307.2549v3|first=Williams|last=Aaron|title=Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2)|year=2013|class=math.CO}}</ref> साइंस फिक्शन लेखक और गणितज्ञ [[ग्रेग एगन]] ने लंबाई एन के सुपरपरमुटेशन का उत्पादन करने के लिए एक प्रारूप  तैयार किया! + (एन−1)! + (एन−2)! + (एन−3)! + एन - 3।<ref name ="Greg Egan"/>2018 तक, ये n ≥ 7 के लिए जाने जाने वाले सबसे छोटे सुपरपरम्यूटेशन थे। हालांकि, 1 फरवरी 2019 को, बोगडान कोंडा ने घोषणा की कि उन्होंने लंबाई 5907, या (n! + (n−1)! + (n−2)! + (n−3)! + n − 3) − 1, जो एक नया रिकॉर्ड था।<ref name="Greg Egan"/>27 फरवरी 2019 को, रॉबिन ह्यूस्टन द्वारा विकसित विचारों का उपयोग करते हुए, ईगन ने लंबाई 5906 के n = 7 के लिए एक सुपरपरमुटेशन का उत्पादन किया।<ref name="Greg Egan"/>क्या n> 7 के मानों के लिए समान छोटे सुपरपरम्यूटेशन भी मौजूद हैं, यह एक खुला प्रश्न है। n = 7 के लिए वर्तमान सर्वोत्तम निचली सीमा (ऊपर अनुभाग देखें) अभी भी 5884 है।
20 अक्टूबर 2018 को, [[सममित समूह]] के [[केली ग्राफ]] के माध्यम से हैमिल्टनियन पथ के निर्माण के लिए हारून विलियम्स द्वारा एक निर्माण को अपनाने तथा ,<ref>{{Cite arXiv|eprint=1307.2549v3|first=Williams|last=Aaron|title=Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2)|year=2013|class=math.CO}}</ref> विज्ञान परिकलन लेखक और गणितज्ञ [[ग्रेग एगन]] ने लंबाई के सुपरपरमुटेशन का उत्पादन करने के लिए ''n''! + (''n''−1)! + (''n''−2)! + (''n''−3)! + ''n'' − 3 एक कलन विधि तैयार किया।  2018 तक, ये n ≥ 7 के लिए जाने जाने वाले सबसे छोटे सुपरपरम्यूटेशन थे। यद्यपि, 1 फरवरी 2019 को, बोगडान कोंडा ने घोषणा की कि उन्होंने एक सुपरपरम्यूटेशन पाया है जिसकी लंबाई 5907, या (n! + (n−1)! + (n−2)! + (n−3)! + n − 3) − 1, है जो एक नया रिकॉर्ड था<ref name="Greg Egan"/>27 फरवरी 2019 को, रॉबिन ह्यूस्टन द्वारा विकसित विचारों का उपयोग करते हुए, ईगन ने लंबाई 5906 के n = 7 के लिए एक सुपरपरमुटेशन का उत्पादन किया <ref name="Greg Egan"/> क्या n> 7 के मानों के लिए समान छोटे सुपरपरम्यूटेशन भी उपलब्ध हैं, यह एक खुला प्रश्न है। n = 7 के लिए वर्तमान सर्वोत्तम निचली सीमा अभी भी 5884 है।


== यह भी देखें ==
== यह भी देखें ==
*[[सुपरपैटर्न]], एक क्रमचय जिसमें क्रमचय पैटर्न के रूप में n प्रतीकों का प्रत्येक क्रमचय शामिल है
*[[सुपरपैटर्न]], एक क्रमचय जिसमें क्रमचय पैटर्न के रूप में n प्रतीकों का प्रत्येक क्रमचय सम्मिलित है।
* डी ब्रुजन अनुक्रम, चक्रीय अनुक्रमों के साथ एक समान समस्या
* डी ब्रुजन अनुक्रम, चक्रीय अनुक्रमों के साथ एक समान समस्या है।


==अग्रिम पठन==
==अग्रिम पठन==
Line 47: Line 48:
* [https://warosu.org/sci/thread/S3751105#p3751197 The 4chan post on /sci/], archived on warosu.org
* [https://warosu.org/sci/thread/S3751105#p3751197 The 4chan post on /sci/], archived on warosu.org
* [https://twitter.com/robinhouston/status/1054637891085918209 Tweet] by Robin Houston, which brought attention to the 4chan post
* [https://twitter.com/robinhouston/status/1054637891085918209 Tweet] by Robin Houston, which brought attention to the 4chan post
[[Category: शब्दों पर कॉम्बिनेटरिक्स]] [[Category: गणनात्मक कॉम्बिनेटरिक्स]] [[Category: क्रमपरिवर्तन]]


[[Category: Machine Translated Page]]
[[Category:CS1 English-language sources (en)]]
[[Category:CS1 maint]]
[[Category:Created On 21/03/2023]]
[[Category:Created On 21/03/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:क्रमपरिवर्तन]]
[[Category:गणनात्मक कॉम्बिनेटरिक्स]]
[[Category:शब्दों पर कॉम्बिनेटरिक्स]]

Latest revision as of 17:00, 27 April 2023

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

यह दिखाया गया है कि 1 ≤ n ≤ 5 के लिए, n प्रतीकों पर सबसे छोटे सुपरपरमुटेशन की लंबाई है 1! + 2! + … + n! ओईआईएस में अनुक्रम A180632 है। पहले चार सबसे छोटे सुपरपरम्यूटेशन की लंबाई 1, 3, 9 और 33 होती है, जिससे शृंखला 1, 121, 123121321, और 123412314231243121342132413214321 बनते हैं। यद्यपि, n = 5 के लिए, 153 की लंबाई वाले कई छोटे सुपरपरमुटेशन होता हैं। ऐसा एक सुपरपरमुटेशन नीचे दिखाया गया है, जबकि शृंखला के दूसरे भाग में सभी चौथे और पांचवे को स्विचन करके समान लंबाई का एक और शृंखला प्राप्त किया जा सकता है।

:[1]1234512341523412534123541231452314253142351423154231245312435124315243125431213452134251342153421354213

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

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

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

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

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

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

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

सितंबर 2011 में, 4चान के विज्ञान और गणित बोर्ड पर एक अज्ञात पोस्टर ने सिद्ध कर दिया कि n प्रतीकों (n ≥ 2) पर सबसे छोटा सुपरपरमुटेशन कम से कम लंबाई n! + (n−1)! + (n−2)! + n − 3 है।[3]जापानी एनिमेए श्रृंखला हारुही सुजुमिया के संदर्भ में, समस्या को द हारुही प्रॉब्लम के रूप में इमेजबोर्ड पर प्रस्तुत किया गया था:[4] यदि आप श्रृंखला के पहले सीज़न के 14 एपिसोड हर संभव क्रम में देखना चाहते हैं, तो आपको एपिसोड की सबसे छोटी कड़ी क्या देखनी होगी?[5] इस निचली सीमा का प्रमाण अक्टूबर 2018 में आम जनता के हित मे आया जब गणितज्ञ और कंप्यूटर वैज्ञानिक रॉबिन ह्यूस्टन द्वारा इसके बारे में ट्वीट किया ।[3] तो 25 अक्टूबर 2018 को, रॉबिन ह्यूस्टन, जे पैनटोन, और विंस वैटर ने इस प्रमाण का एक परिष्कृत संस्करण इंटेगर अनुक्रमों के ऑन-लाइन विश्वकोश (ओईआईएस) में प्रकाशित किया।[5][6] इस प्रमाण का एक प्रकाशित संस्करण, लिए एंगेन और वैटर 2019 में दिखाई देता है, जिसका श्रेय अज्ञात 4चान पोस्टर को दिया जाता है, विशेष रूप से "द हारुही प्रॉब्लम" के लिए(14 प्रतीकों के स्थिति) [7]वर्तमान निचली और ऊपरी सीमा क्रमशः 93,884,313,611 और 93,924,230,411 है।।[3]इसका अर्थ है कि श्रृंखला को हर संभव क्रम में देखने में लगभग 4 मिलियन वर्ष लगेंगे।

ऊपरी सीमा

20 अक्टूबर 2018 को, सममित समूह के केली ग्राफ के माध्यम से हैमिल्टनियन पथ के निर्माण के लिए हारून विलियम्स द्वारा एक निर्माण को अपनाने तथा ,[8] विज्ञान परिकलन लेखक और गणितज्ञ ग्रेग एगन ने लंबाई के सुपरपरमुटेशन का उत्पादन करने के लिए n! + (n−1)! + (n−2)! + (n−3)! + n − 3 एक कलन विधि तैयार किया। 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 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=144015’