🔢 mathematics

A More Efficient Algorithm for Finding the Number of Permutations of $\mathbb{ZZ}/n\mathbb{ZZ}$ with Distinct Partial Sums

यह शोध पत्र $\mathbb{Z}/n\mathbb{Z}$ के उन क्रमपरिवर्तनों (permutations) की गणना करने के लिए एक उन्नत एल्गोरिदम प्रस्तुत करता है जिनके आंशिक योग (partial sums) विशिष्ट होते हैं, विशेष रूप से $n=20$ और $n=22$ के लिए परिणाम ज्ञात करता है, और साथ ही एक ज्ञात अनुक्रम (sequence) के साथ एक एकैकी संबंध (bijection) स्थापित करता है जो नए पदों की व्युत्पत्ति को सक्षम बनाता है।

मूल लेखक: Quinn Baker, Amy Feaver

प्रकाशित 2026-07-27

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Quinn Baker, Amy Feaver

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक विशाल पार्टी में हैं जहाँ हर किसी की शर्ट पर एक अनूठा नंबर है, जो 0 से लेकर एक विशिष्ट सीमा तक है। मेजबान चाहता है कि मेहमानों को एक फोटो के लिए एक सीधी रेखा में व्यवस्थित किया जाए, लेकिन एक पेचीदा नियम है: जैसे-जैसे आप लाइन में आगे बढ़ते हैं, आपको अब तक देखे गए नंबरों का एक चलता हुआ योग (रनिंग टैली) रखना होगा। नियम यह है कि हर बार जब आप टैली में एक नया व्यक्ति जोड़ते हैं, तो नया कुल योग एक ऐसा नंबर होना चाहिए जो आपने पूरी लाइन में पहले कभी नहीं देखा हो। यदि आप ऐसे कुल योग पर पहुँच जाते हैं जिसे आपने पहले ही गिन लिया है, तो लाइन टूट जाती है और फोटो खराब हो जाता है। यह केवल एक पार्टी गेम नहीं है; यह गणित की दुनिया में "ग्रुप थ्योरी" (समूह सिद्धांत) से जुड़ा एक गहरा पहेली है, जो विशेष रूप से संख्याओं को एक घेरे (जैसे घड़ी के घंटे) में व्यवस्थित करने से संबंधित है, ताकि हमारे चलते हुए योग कभी दोहराए न जाएँ जब तक कि हमने प्रत्येक संख्या का ठीक एक बार उपयोग न कर लिया हो। गणितज्ञों को इसकी परवाह है क्योंकि यह उन्हें ब्रह्मांड में समरूपता और व्यवस्था की छिपी हुई संरचनाओं को समझने में मदद करता है, और इन विशेष लाइनों को खोजना आश्चर्यजनक रूप से कठिन है, जैसे कि सुई के ढेर में एक विशिष्ट सुई खोजने की कोशिश करना जिसका आकार बदलता रहता है।

यह शोध पत्र इस बारे में है कि कैसे गणितज्ञों की एक टीम ने कुछ प्रकार के नंबर सर्कल्स के लिए इस "रनिंग टोटल" पहेली को हल करने का एक बहुत अधिक स्मार्ट तरीका खोजा। उन्होंने उन सर्कल्स पर ध्यान केंद्रित किया जिनमें सम संख्या में स्थान होते हैं, जैसे कि 20 या 22 घंटों वाली घड़ी। अतीत में, इन सर्कल्स के लिए वैध लाइनों की संख्या ज्ञात करने के लिए, कंप्यूटरों को लगभग हर संभव व्यवस्था की एक-एक करके जाँच करनी पड़ती थी। यह एक अच्छी फोटो खोजने के लिए लोगों के हर संभावित संयोजन को लाइन में खड़े होने के लिए पूछने जैसा था, जिसमें बहुत समय लगता है और जैसे-जैसे पार्टी बड़ी होती जाती है, यह असंभव होता जाता है। लेखकों, बेकर और फीवर ने एक नया एल्गोरिदम पेश किया जो एक अत्यंत बुद्धिमान 'बाउंसर' की तरह काम करता है। लाइन के अंत तक यह देखने के बजाय कि क्या फोटो खराब हो गया है, यह बाउंसर हर एक व्यक्ति के शामिल होने के बाद रनिंग टोटल की जाँच करता है। जैसे ही बाउंसर एक ऐसा कुल योग देखता है जो पहले ही दिखाई दे चुका है, वह तुरंत उस लाइन को आगे बढ़ने से रोक देता है। वे महसूस करते हैं कि यदि एक छोटी लाइन टूट जाती है, तो उस समान टूटे हुए आरंभ से शुरू होने वाली हर लंबी लाइन भी बर्बाद होने के लिए ही बनी है। इन "खराब" शाखाओं को जल्दी काट कर, वे बहुत सारा समय बचा लेते हैं।

इस कुशल पद्धति का उपयोग करते हुए, टीम ने 20 और 22 स्थानों वाले सर्कल्स के लिए वैध लाइनों की सटीक संख्या की गणना की। उन्होंने पाया कि 20-स्पॉट सर्कल के लिए, मेहमानों को व्यवस्थित करने के ठीक 5,074,931,072 तरीके हैं। 22-स्पॉट सर्कल के लिए, यह संख्या चौंका देने वाली 298,557,044,000 तक पहुँच जाती है। ये संख्याएँ इतनी बड़ी थीं कि उन्हें सही होने के लिए एक अन्य गणितज्ञ, बर्ट डोबलेरे द्वारा स्वतंत्र रूप से सत्यापित किया जाना पड़ा। यह पत्र इन "रनिंग टोटल" लाइनों और "डिफरेंस सेट्स" नामक एक अन्य अवधारणा के बीच एक दिलचस्प संबंध को भी सिद्ध करता है, यह दिखाते हुए कि एक को गिनना दूसरे को गिनने के बिल्कुल समान है। यह प्रमाण उन्हें एक की विशेषताओं का उपयोग करके दूसरे को हल करने की अनुमति देता है, जिससे उनकी दक्षता दोगुनी हो जाती है।

लेखक इन संख्याओं को लेकर बहुत आश्वस्त हैं क्योंकि ये एक कठोर गणितीय प्रमाण और एक व्यवस्थित रूप से असंभव विकल्पों को हटाने वाली कंप्यूटर खोज से प्राप्त हुई हैं। हालाँकि, वे सावधानीपूर्वक यह भी नोट करते हैं कि हालांकि उनकी विधि इन व्यवस्थाओं को गिनने का सबसे तेज़ ज्ञात तरीका है, फिर भी यह समस्या अत्यंत कठिन है। जैसे-जैसे सर्कल में स्थानों की संख्या बढ़ती है, संभावित व्यवस्थाओं की संख्या इतनी तेज़ी से बढ़ती है कि उनका स्मार्ट बाउंसर भी हमेशा उनका साथ नहीं दे पाता। वे सुझाव देते हैं कि वैध लाइनों और सभी संभावित लाइनों का अनुपात छोटा होता जाता है, जो आकार में प्रत्येक अगले कदम के साथ लगभग दस गुना कम हो जाता है। हालांकि उन्होंने किसी भी आकार के लिए तुरंत उत्तर बताने वाला कोई जादुई फॉर्मूला नहीं खोजा है, उनका कार्य यह सिद्ध करता है कि यह समझकर कि कब खोज को रोकना है, हम अपनी जानकारी की सीमाओं को पहले से कहीं अधिक आगे बढ़ा सकते हैं। वे इस विचार के साथ समाप्त करते हैं कि आगे बढ़ने का सबसे अच्छा तरीका शायद इन "स्मार्ट शॉर्टकट" को खोजना है ताकि ज्ञात समाधानों को अन्य सभी से मैप किया जा सके, लेकिन फिलहाल, उनका नया एल्गोरिदम इन गणितीय उत्कृष्ट कृतियों को गिनने के लिए हमारे पास उपलब्ध सबसे शक्तिशाली उपकरण है।

तकनीकी सारांश: $\mathbb{Z}/n\mathbb{Z}$ के क्रमचय (Permutations) की संख्या खोजने के लिए एक अधिक कुशल एल्गोरिदम

समस्या विवरण
यह शोध पत्र पूर्णांकों के योग समूह (additive group) $\mathbb{Z}/n\mathbb{Z}$ के भीतर विशिष्ट क्रमचयों (permutations) की गणना को संबोधित करता है, जहाँ $n$ एक सम पूर्णांक है। मुख्य समस्या उन क्रमचयों $\sigma = (\sigma_0, \sigma_1, \dots, \sigma_{n-1})$ की संख्या गिनने की है जहाँ आंशिक योग (या समूह के संदर्भ में "फैक्टोरियल्स") सभी भिन्न होते हैं। विशेष रूप से, यह शोध पत्र 'ऑन-लाइन एनसाइक्लोपीडिया ऑफ इंटीजर सीक्वेंसेज' (OEIS) की अनुक्रम A141599 पर ध्यान केंद्रित करता है, जो $\mathbb{Z}/2k\mathbb{Z}$ के क्रमचयों के लिए "डिफरेंस सेट्स" (difference sets) की गणना करता है जिनमें भिन्न अंतर (distinct differences) होते हैं।

एक क्रमचय में "भिन्न अंतर" तब होते हैं जब अंतरों का सेट $d_i \equiv \sigma_i - \sigma_{i-1} \pmod n$ (जहाँ $1 \le i \le n-1$ ) $\mathbb{Z}/n\mathbb{Z}$ के प्रत्येक गैर-शून्य तत्व को ठीक एक बार समाहित करता है। लेखक नोट करते हैं कि ऐसे क्रमचय केवल तभी मौजूद होते हैं जब $n$ सम हो। कम्प्यूटेशनल चुनौती यह है कि कुल क्रमचयों की संख्या ( $n!$ ) फैक्टोरियल दर से बढ़ती है, जिससे बड़े $n$ के लिए ब्रूट-फोर्स गणना (brute-force enumeration) अव्यवहारिक हो जाती है।

कार्यप्रणाली
लेखक एक रिकर्सिव बैकट्रैकिंग एल्गोरिदम प्रस्तावित करते हैं जो खोज स्थान (search space) को जल्दी से छाँटकर (pruning) पिछले ब्रूट-फोर्स दृष्टिकोणों की तुलना में काफी सुधार करता है। कार्यप्रणाली तीन मुख्य स्तंभों पर आधारित है:

डिफरेंस सेट्स और सीक्वेंसिंग के बीच बाइजेक्शन (Bijection):
शोध पत्र "डिफरेंस सेट्स विद डिस्टिंक्ट डिफरेंसेस" और $\mathbb{Z}/n\mathbb{Z}$ की "सीक्वेंसिंग" के बीच एक औपचारिक बाइजेक्शन (थ्योरम 1) स्थापित करता है। एक सीक्वेंसिंग को एक ऐसे क्रमचय के रूप में परिभाषित किया गया है जहाँ आंशिक योग $s(\sigma, i) = \sum_{j=0}^i \sigma_j$ सभी भिन्न होते हैं। प्रमाण यह प्रदर्शित करता है कि एक डिफरेंस सेट $D_\tau = (d_1, \dots, d_{n-1})$ को एक सीक्वेंसिंग $\sigma = (0, d_1, \dots, d_{n-1})$ में मैप किया जा सकता है, और इसके विपरीत भी। यह लेखकों को सीधे डिफरेंस सेट्स को गिनने के बजाय सीक्वेंसिंग्स को गिनने की अनुमति देता है।
गुणन द्वारा समरूपता न्यूनीकरण (Symmetry Reduction via Multiplication):
लेम्मा 2 का लाभ उठाते हुए, लेखक इस गुण का उपयोग करते हैं कि यदि $\sigma$ एक सीक्वेंसिंग है और $r$ एक पूर्णांक है जो $n$ के साथ सह-अभाज्य (coprime) है ( $\gcd(r, n) = 1$ ), तो तत्व-वार गुणन (element-wise product) $(r\sigma_0, r\sigma_1, \dots, r\sigma_{n-1})$ भी एक सीक्वेंसिंग है। यह एल्गोरिदम को एक विशिष्ट "शाखा" (जैसे $0, 1 $से शुरू होने वाले क्रमचय) के लिए सीक्वेंसिंग्स की गणना करने और अन्य शाखाओं को कवर करने के लिए यूलर टोटिएंट फंक्शन$ \phi(n/d)$ से गुणा करने की अनुमति देता है, बजाय इसके कि उन्हें व्यक्तिगत रूप से गणना किया जाए।
रिकर्सिव ब्रांच प्रूनिंग (एल्गोरिदम 2):
नया एल्गोरिदम एक रिकर्सिव सर्च है जो आंशिक क्रमचयों (partial permutations) का निर्माण करता है। पिछले ब्रूट-फोर्स तरीकों के विपरीत, जो पूर्ण क्रमचयों को मान्य (validate) करते थे, यह एल्गोरिदम "आंशिक योगों" (partials) की स्थिति को बनाए रखता है।

प्रूनिंग लॉजिक: यदि किसी नए तत्व को आंशिक क्रमचय में जोड़ने से ऐसा आंशिक योग प्राप्त होता है जो पहले देखा जा चुका है (या समय से पहले 0 के बराबर है), तो उस शाखा को तुरंत छोड़ दिया जाता है।
दक्षता: यह सुनिश्चित करता है कि एल्गोरिदम उन $(n-k)!$ क्रमचयों की खोज न करे जो एक अमान्य आंशिक अनुक्रम को आगे बढ़ाएंगे। उदाहरण के लिए, $\mathbb{Z}/20\mathbb{Z}$ में, आंशिक अनुक्रम $(0, 1, 19)$ इंडेक्स 2 पर 0 का आंशिक योग देता है, जो अमान्य है; एल्गोरिदम इस पूरी शाखा को त्याग देता है, जिससे $17!$ संभावित कॉल्स बच जाते हैं।

मुख्य योगदान

OEIS A141599 के लिए नए पद: सुधरे हुए एल्गोरिदम का उपयोग करते हुए, लेखकों ने अनुक्रम (जो $n=20, 22, 24$ $n = 20, 22, 24$ के अनुरूप है) के 10वें, 11वें और 12वें पदों की गणना की। मान हैं:
- $n=20$ : 5,074,931,072
- $n=22$ : 298,557,044,000
- $n=24$ : 21,224,961,132,544
  10वें और 11वें पदों को बर्ट डोबलेरे द्वारा स्वतंत्र रूप से सत्यापित किया गया था।
सैद्धांतिक एकीकरण: शोध पत्र डिफरेंस सेट्स और सीक्वेंसिंग्स के बीच बाइजेक्शन का एक कठोर प्रमाण प्रदान करता है, जो क्लासिकल परिणामों (गिल्बर्ट, गॉर्डन) को वर्तमान कम्प्यूटेशनल दृष्टिकोण के साथ एकीकृत करता है।
एल्गोरिथमिक अनुकूलन: आंशिक योग टकराव (partial sum collisions) के आधार पर प्रारंभिक समाप्ति के साथ रिकर्सिव ब्रांच सर्च का परिचय इस विशिष्ट गणना समस्या के लिए अब तक का सबसे कुशल ज्ञात तरीका है।

परिणाम और डेटा विश्लेषण
शोध पत्र $n=22$ तक सम $n$ के लिए सीक्वेंसिंग्स की संख्या और कुल क्रमचयों ( $n!$ ) के बीच तुलना (तालिका 1 और 2) प्रस्तुत करता है। परिणाम दर्शाते हैं कि जैसे-जैसे $n$ बढ़ता है, कुल क्रमचयों के अनुपात में सीक्वेंसिंग्स का अनुपात सख्ती से और तेजी से घटता है, जो प्रत्येक चरण के साथ लगभग एक परिमाण (order of magnitude) गिर जाता है। $n=22$ के लिए, अनुपात लगभग $2.66 \times 10^{-10}$ है।

यह अनुभवजन्य साक्ष्य प्रूनिंग रणनीति की प्रभावकारिता का समर्थन करता है। चूंकि सभी क्रमचयों के स्थान के भीतर वैध सीक्वेंसिंग्स अत्यंत विरल (sparse) हैं, इसलिए पूर्ण क्रमचयों को उत्पन्न करना और मान्य करना अक्षम है। रिकर्सिव दृष्टिकोण, जो अमान्य आंशिक पथों को तुरंत समाप्त कर देता है, देखी गई विरलता के अनुरूप है।

महत्व और दावे
लेखक दावा करते हैं कि उनका एल्गोरिदम अनुक्रम A141599 के पदों की गणना के लिए अब तक का सबसे कुशल ज्ञात तरीका है। उनका तर्क है कि हालांकि समय जटिलता (time complexity) सुपर-पॉलिनोमियल बनी हुई है (संभवतः घातीय से बदतर लेकिन $O(n!)$ से बेहतर), प्रूनिंग तकनीक ब्रूट-फोर्स विधियों की तुलना में "सख्त सुधार" (strict improvement) प्रदान करती है क्योंकि यह अमान्य शाखाओं पर बर्बाद होने वाली गणना को रोकती है।

शोध पत्र विनम्रतापूर्वक निष्कर्ष निकालता है कि यदि नए गणितीय रूपांतरणों (transformations) की पहचान नहीं की जाती है, तो गणना एल्गोरिदम में और सुधार की संभावना सीमित है। विशेष रूप से, वे सुझाव देते हैं कि भविष्य की प्रगति सह-अभाज्य पूर्णांकों द्वारा गुणन (beyond multiplication by coprime integers) से परे पूर्ण रूपांतरणों के सेट की पहचान करने पर निर्भर हो सकती है, जो संभावित रूप से गहन खोज (exhaustive search) की आवश्यकता को पूरी तरह से समाप्त कर सकती है। हालाँकि, वे इस कार्य में ऐसे रूपांतरण प्रस्तावित नहीं करते हैं, यह नोट करते हुए कि वर्तमान रिकर्सिव दृष्टिकोण परिभाषित समस्या को हल करने के लिए 'स्टेट-ऑफ-द-आर्ट' है।

इसी तरह के और पेपर