🔢 mathematics

Universal cycle constructions for k-subsets and k-multisets

यह शोध पत्र एक नए प्रतिनिधित्व को पेश करके k-उपसमुच्चयों (k-subsets) और k-बहु-समुच्चयों (k-multisets) के लिए प्रथम ज्ञात कुशल सार्वभौमिक चक्र (universal cycle) निर्माण प्रस्तुत करता है, जो सभी n और k ≥ 2 के लिए क्रमशः O(n) समय प्रति प्रतीक और O(1) परिशोधित (amortized) समय प्रति प्रतीक में इन अनुक्रमों को उत्पन्न करने के लिए उत्तराधिकारी-नियम (successor-rule) और नेकलेस संयोजन (necklace concatenation) एल्गोरिदम को सक्षम बनाता है।

मूल लेखक: Colin Campbell, Luke Janik-Jones, Joe Sawada

प्रकाशित 2026-03-13

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

CC BY 4.0

मूल लेखक: Colin Campbell, Luke Janik-Jones, Joe Sawada

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

कल्पना कीजिए कि आपके पास मोतियों से बना एक विशाल, जादुई हार है। प्रत्येक मोती एक विशिष्ट संयोजन (combination) का प्रतिनिधित्व करता है जिसे आप एक बॉक्स से चुन सकते हैं। आपका लक्ष्य इन मोतियों को एक एकल, निरंतर लूप में पिरोना है ताकि हर संभव संयोजन इस हार के एक छोटे से हिस्से के रूप में ठीक एक बार दिखाई दे।

गणित की दुनिया में, इस जादुई लूप को यूनिवर्सल साइकिल (Universal Cycle) कहा जाता है।

यूनफर्सेटी ऑफ गुएल्फ़फ के शोधकर्ताओं द्वारा लिखा गया यह शोध पत्र, दो विशिष्ट प्रकार के संयोजनों के लिए इन लूपों को कुशलतापूर्वक बनाने की एक कठिन समस्या पर चर्चा करता है:

k-सबसेट्स (k-subsets): $n$ वस्तुओं की सूची में से $k$ अलग-अलग वस्तुएं चुनना (जैसे 5 फलों की टोकरी से 3 अलग फल चुनना)।
k-मल्टीसेट्स (k-multisets): $k$ वस्तुएं चुनना जहाँ आप दोहराव कर सकते हैं (जैसे 5 फलों की टोकरी से 3 फल चुनना, लेकिन आप तीन सेब चुन सकते हैं)।

समस्या: "गलत भाषा"

लंबे समय तक, गणितज्ञों ने एक "मानक भाषा" का उपयोग करके इन हारों को बनाने की कोशिश की।

सबसेट्स के लिए, उन्होंने उन्हें सरल सूचियों के रूप में लिखने की कोशिश की (जैसे, {1, 2} बनता है 12 या 21)।
मल्टीसेट्स के लिए, उन्होंने भी उन्हें सूचियों के रूप में लिखने की कोशिश की (जैसे, {1, 1, 2} बनता है 112, 121, या 211)।

चुनौती: इस मानक भाषा में, हार अक्सर अटक जाता है। यह ऐसा है जैसे आप चौकोर पहियों वाली कार चलाने की कोशिश कर रहे हों; कभी-कभी यह काम करता है, लेकिन अक्सर एक सुचारू, निरंतर लूप बनाना असंभव होता है जो हर स्थान पर ठीक एक बार जाए। गणित कहता है, "आप ऐसा नहीं कर सकते जब तक कि संख्याएँ पूरी तरह से मेल न खा जाएँ," जो कि बहुत कम होता है।

समाधान: एक नया "गुप्त कोड"

लेखकों ने महसूस किया कि समस्या हार की नहीं थी, बल्कि उस भाषा की थी जिसका उपयोग हम इन संयोजनों को वर्णित करने के लिए कर रहे थे। उन्होंने इन संयोजनों को संख्याओं की स्ट्रिंग्स में बदलने का एक नया तरीका ईजाद किया, जो एक गुप्त कोड की तरह काम करता है और किसी भी संख्या में वस्तुओं के लिए इस लूप को संभव बनाता है।

1. "डिफरेंस कोड" (सबसेट्स के लिए)

वस्तुओं को सीधे सूचीबद्ध करने के बजाय, वे उनके बीच की दूरी को सूचीबद्ध करते हैं।

पुराना तरीका: सेट {1, 3, 4} को 1, 3, 4 के रूप में लिखा जाता है।
नया तरीका: पहले नंबर से शुरू करें, फिर वह लिखें जिसे आप अगले नंबर तक पहुँचने के लिए जोड़ते हैं।
- 1 से शुरू करें।
- 3 तक पहुँचने के लिए, 2 जोड़ें।
- 4 तक पहुँचने के लिए, 1 जोड़ें।
- परिणाम: 1, 2, 1

यह "डिफरेंस कोड" अलग-अलग वस्तुओं को चुनने की उलझी हुई समस्या को छोटी संख्याओं को जोड़ने वाली एक साफ-सुथरी पहेली में बदल देता है। अचानक, "चौकोर पहिए" गोल हो जाते हैं, और लूप संभव हो जाता है।

2. "फ्रीक्वेंसी कोड" (मल्टीसेट्स के लिए)

उन वस्तुओं के लिए जहाँ आप विकल्पों को दोहरा सकते हैं, उन्होंने एक "टैली शीट" दृष्टिकोण का उपयोग किया।

पुराना तरीका: {1, 1, 2} को 1, 1, 2 के रूप में लिखा जाता है।
नया तरीका: गिनें कि आपके पास प्रत्येक वस्तु कितनी है, लेकिन अंतिम वस्तु से पहले रुक जाएँ (क्योंकि अंतिम वस्तु स्पष्ट होती है)।
- कितने 1 हैं? 2।
- कितने 2 हैं? 1।
- (हमें 3 के बारे में लिखने की आवश्यकता नहीं है क्योंकि हम जानते हैं कि कुल योग 3 है)।
- परिणाम: 2, 1

यह समस्या को एक सरल गिनती के खेल में बदल देता है जो हमेशा एक समाधान प्रदान करता है।

जादुई ट्रिक: लूप को तेजी से बनाना

लूप खोजना एक बात है; इसे तेजी से बनाना दूसरी बात है। कल्पना कीजिए कि आप एक विशाल भूलभुलैया में एक समूह का नेतृत्व करने वाले टूर गाइड हैं।

धीमा तरीका: आप पूरी भूलभुलैया का नक्शा याद कर सकते हैं (जिसमें बहुत अधिक मेमोरी लगती है) और हर बार अपना नक्शा देखते हुए कदम-दर-कदम चल सकते हैं।
लेखकों का तरीका: उन्होंने स्थानीय नियमों (एक GPS की तरह) का एक सेट बनाया।
- नियम: "यदि आप इस स्थान पर हैं, तो अपने पिछले कुछ कदमों को देखें। यदि आपको कोई पैटर्न दिखता है, तो बाएं मुड़ें। यदि नहीं, तो दाएं मुड़ें।"
- क्योंकि नियम इतने सरल हैं, टूर गाइड (कंप्यूटर) बिना पूरे नक्शे को याद किए लगभग तुरंत अगला कदम तय कर सकता है।

उन्होंने इसे करने के दो तरीके सिद्ध किए:

"अगला कदम" नियम: आप पलक झपकते ही (विशेष रूप से, समस्या के आकार के अनुपात में लगने वाले समय में) अनुक्रम में अगला नंबर निकाल सकते हैं।
"नेकलेस स्टिचिंग" विधि: कल्पना करें कि आपके पास पहले से बने कई छोटे, पूर्ण लूप (हार) हैं। लेखकों ने उन्हें एक चेन की तरह आपस में जोड़ने का तरीका खोजा, जिससे एक विशाल लूप बन सके। उन्होंने दिखाया कि यदि आप उन्हें एक विशिष्ट क्रम में जोड़ते हैं (जैसे किताब को उल्टा पढ़ते हुए), तो आप अगले मोती को तुरंत उत्पन्न कर सकते हैं।

यह क्यों महत्वपूर्ण है

इस शोध पत्र से पहले, हमारे पास मल्टीसेट्स (दोहराई जाने वाली वस्तुओं) के लिए इन लूपों को कुशलतापूर्वक उत्पन्न करने का कोई तरीका नहीं था। यह ऐसा था जैसे हमारे पास केक बनाने की रेसिपी तो है लेकिन ओवन नहीं है। अब, हमारे पास एक काम करने वाला ओवन है जो रसोई कितनी भी बड़ी क्यों न हो, केक को तुरंत बेक कर सकता है।

संक्षेप में:
लेखकों ने एक कठिन गणितीय पहेली ली, महसूस किया कि टुकड़ों को वर्णित करने का पुराना तरीका टूटा हुआ था, उन्हें वर्णित करने के लिए एक चतुर नया "कोड" बनाया, और फिर उन सभी को एक पूर्ण, अनंत लूप में पिरोने के लिए एक तेज़, मेमोरी-कुशल मशीन बनाई। मल्टीसेट्स के लिए कुशलतापूर्वक ऐसा लूप बनाने में यह पहली बार है कि कोई सफल हुआ है।

यहाँ कैंपबेल, जेनिक-जोन्स और सावाडा के शोध पत्र "Universal cycle constructions for k-subsets and k-multisets" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र दो मौलिक कॉम्बिनेटोरियल सेट्स (combinatorial sets) के लिए यूनिवर्सल साइकल (U-cycles) के निर्माण को संबोधित करता है:

$[n] = \{1, 2, \dots, n\}$ के $k$ -subsets, जिन्हें $S_k(n)$ के रूप में दर्शाया गया है।
$[n]$ के $k$ -multisets, जिन्हें $M_k(n)$ के रूप में दर्शाया गया है।

एक यूनिवर्सल साइकिल (U-cycle) एक चक्रीय अनुक्रम (cyclic sequence) है जिसकी लंबाई $|S|$ होती है और जिसमें सेट $S$ का प्रत्येक तत्व ठीक एक बार एक सबस्ट्रिंग (substring) के रूप में आता है। मुख्य चुनौती जो पहचानी गई है वह यह है कि इन वस्तुओं के लिए प्रतिनिधित्व का चयन (choice of representation) अत्यंत महत्वपूर्ण है।

मानक प्रतिनिधित्व (Standard Representations): मानक स्ट्रिंग रूपों (जैसे कि सबसेट के क्रमपरिवर्तन या फ्रीक्वेंसी मैप्स) का उपयोग करने से अक्सर U-cycles का अस्तित्व नहीं रहता, जब तक कि विशिष्ट विभाज्यता शर्तें (divisibility conditions) पूरी न हों (जैसे कि $n$ का $\binom{n}{k}$ को विभाजित करना)। भले ही वे मौजूद हों, कुशल निर्माण (efficient constructions) मिलना कठिन रहा है।
मौजूदा अंतराल (Existing Gaps): हालांकि ग्राफ-सैद्धांतिक प्रमाणों (लेबल वाले ग्राफ का उपयोग करके) ने इन सेट्स के लिए U-cycles के अस्तित्व को सिद्ध किया है, लेकिन उनमें कुशल रचनात्मक एल्गोरिदम (efficient constructive algorithms) का अभाव था। विशेष रूप से, $k$ -multisets के लिए कोई ज्ञात कुशल निर्माण उपलब्ध नहीं थे।

2. कार्यप्रणाली (Methodology)

लेखक डिफरेंस रिप्रेजेंटेशन (difference representations) और बाउंडेड-वेट डी ब्रुइन सीक्वेंस (bounded-weight de Bruijn sequences) पर आधारित एक नवीन दृष्टिकोण प्रस्तावित करते हैं।

A. नवीन प्रतिनिधित्व (Novel Representations)

मानक प्रतिनिधित्व के बजाय, शोध पत्र विशिष्ट स्ट्रिंग एनकोडिंग पेश करता है जो कॉम्बिनेटोरियल वस्तुओं को बाउंडेड वेट (bounded weight) वाली स्ट्रिंग्स में मैप करती है:

$k$ -subsets के लिए डिफरेंस रिप्रेजेंटेशन:
- एक सबसेट $\{s_1, s_2, \dots, s_k\}$ (क्रमबद्ध) को एक स्ट्रिंग $d_1 d_2 \dots d_k$ में मैप किया जाता है जहाँ $d_1 = s_1$ और $i > 1$ के लिए $d_i = s_i - s_{i-1}$ है।
- यह $S_k(n)$ को $\{1, \dots, n-k+1\}$ वर्णमाला (alphabet) पर लंबाई $k$ की स्ट्रिंग्स में मैप करता है जिनका कुल भार (कुल योग) $n$ द्वारा सीमित है।
$k$ -multisets के लिए शॉर्टहैंड फ्रीक्वेंसी रिप्रेजेंटेशन:
- एक मल्टीसेट को एक फ्रीक्वेंसी मैप $f_1 f_2 \dots f_n$ (जहाँ $\sum f_i = k$ ) द्वारा दर्शाया जाता है। अंतिम प्रतीक $f_n$ अनावश्यक है और उसे छोड़ दिया जाता है, जिससे $\{0, \dots, k\}$ वर्णमाला पर लंबाई $n-1$ की एक स्ट्रिंग प्राप्त होती है जिसका भार $k$ द्वारा सीमित है।
$k$ -multisets के लिए डिफरेंस रिप्रेजेंटेशन:
- यह सबसेट्स के समान है लेकिन 0 सहित एक ग्राउंड सेट पर परिभाषित है, जो $\{0, \dots, n-1\}$ वर्णमाला पर लंबाई $k$ की स्ट्रिंग्स में मैप होता है जिसका भार $n-1$ द्वारा सीमित है।

B. सैद्धांतिक ढांचा: बाउंडेड-वेट डी ब्रुइन सीक्वेंस (Theoretical Framework: Bounded-Weight de Bruijn Sequences)

लेखक $k$ -subsets के लिए U-cycles के निर्माण की समस्या को बाउंडेड-वेट डी ब्रुइन सीक्वेंस (ऐसी स्ट्रिंग्स के लिए यूनिवर्सल साइकिल जिनकी लंबाई $n$ है और वर्णमाला $\Sigma_t$ पर उनके प्रतीकों का योग $\le w$ है) के निर्माण में परिवर्तित कर देते हैं।

साइकिल-जॉइनिंग ट्री (Cycle-Joining Trees): वे साइकिल-जॉइनिंग प्रक्रिया का उपयोग करते हैं, जहाँ अलग-अलग चक्रों (necklaces) को कंजुगेट पेयर्स (conjugate pairs) का उपयोग करके एक एकल U-cycle में जोड़ा जाता है।
सक्सेसर रूल्स (Successor Rules): वे निम्नलिखित के आधार पर विशिष्ट सक्सेसर रूल्स (अगले प्रतीक को निर्धारित करने वाले फलन) परिभाषित करते हैं:
1. "फर्स्ट नॉन-जीरो" पैरेंट रूल (The "First Non-Zero" Parent Rule): "ग्रैंडमामा" (Grandmama) डी ब्रुइन सीक्वेंस निर्माण का एक सामान्यीकरण।
2. मिसिंग सिंबल रजिस्टर (MSR): फिक्स्ड-वेट बाधाओं के लिए तैयार किया गया एक फीडबैक शिफ्ट रजिस्टर तंत्र।

C. एल्गोरिद्मिक रणनीतियाँ (Algorithmic Strategies)

दो प्राथमिक एल्गोरिद्मिक दृष्टिकोण विकसित किए गए हैं:

नेकलैस कॉनकेटेनेशन (Necklace Concatenation) (Amortized $O(1)$ ):
- U-cycle का निर्माण कोलेक्सिकोग्राफिक ऑर्डर (colexicographic order) में नेकलेस के एपीरियॉडिक प्रीफिक्स (aperiodic prefixes) (लघुतम रोटेशन) को जोड़कर किया जाता है।
- इसे एक "कॉनकेटेनेशन ट्री" (एक विशिष्ट साइकिल-जॉइनिंग ट्री का क्रम) के ट्रैवर्सल के माध्यम से लागू किया जाता है।
- जटिलता (Complexity): प्रति प्रतीक $O(1)$ एमॉर्टाइज्ड समय, $O(n)$ स्पेस।
सक्सेसर रूल (Successor Rule) (Deterministic $O(n)$ ):
- एक सीधा फलन $h(\alpha)$ वर्तमान स्ट्रिंग $\alpha$ को देखते हुए अगला प्रतीक कंप्यूट करता है।
- यह जाँचता है कि क्या वर्तमान स्ट्रिंग साइकिल-जॉइनिंग ट्री में एक विशिष्ट कंजुगेट पेयर का हिस्सा है।
- जटिलता (Complexity): प्रति प्रतीक $O(n)$ समय, $O(n)$ स्पेस।

3. मुख्य योगदान (Key Contributions)

$k$ -Multisets के लिए प्रथम कुशल निर्माण: यह शोध पत्र सभी $n, k \ge 2$ के लिए $k$ -multisets के यूनिवर्सल साइकल बनाने के लिए ज्ञात पहले कुशल एल्गोरिदम प्रदान करता है।
एकीकृत ढांचा (Unified Framework): यह प्रदर्शित करता है कि $k$ -subsets और $k$ -multisets के लिए U-cycles, बाउंडेड-वेट डी ब्रुइन सीक्वेंस के विशेष मामले हैं, जो उनके निर्माण को एक ही सैद्धांतिक छत्र के नीचे एकीकृत करते हैं।
ग्रैंडमा सीक्वेंस का सामान्यीकरण: लेखक "ग्रैंडमामा" डी ब्रुइन सीक्वेंस (जो पहले बाइनरी या अनवेटेड मामलों के लिए ज्ञात था) को मनमाने वर्णमाला और ऊपरी भार सीमाओं के साथ सामान्यीकृत करते हैं, और सिद्ध करते हैं कि इसे $O(1)$ एमॉर्टाइज्ड समय में बनाया जा सकता है।
MSR-आधारित निर्माण: एक नवीन निर्माण जो मिसिंग सिंबल रजिस्टर (MSR) का उपयोग करता है, जो फिक्स्ड-वेट बाधाओं के लिए एक वैकल्पिक कुशल विधि प्रदान करता है।

4. परिणाम (Results)

शोध पत्र U-cycles के अस्तित्व और निर्माण के संबंध में तीन मुख्य प्रमेय स्थापित करता है:

$k$ -subsets ( $S_k(n)$ ) के लिए:
- डिफरेंस रिप्रेजेंटेशन का उपयोग करके U-cycles मौजूद हैं।
- उन्हें $O(1)$ एमॉर्टाइज्ड समय प्रति प्रतीक (नेकलैस कॉनकेटेनेशन के माध्यम से) या $O(n)$ समय प्रति प्रतीक (सक्सेसर रूल के माध्यम से) में उत्पन्न किया जा सकता है।
$k$ -multisets ( $M_k(n)$ ) के लिए - शॉर्टहैंड फ्रीक्वेंसी:
- शॉर्टहैंड फ्रीक्वेंसी रिप्रेजेंटेशन का उपयोग करके U-cycles मौजूद हैं।
- इन्हें $O(1)$ एमॉर्टाइज्ड समय प्रति प्रतीक में उत्पन्न किया जा सकता है।
$k$ -multisets ( $M_k(n)$ ) के लिए - डिफरेंस:
- डिफरेंस रिप्रेजेंटेशन का उपयोग करके U-cycles मौजूद हैं।
- इन्हें $O(1)$ एमॉर्टाइज्ड समय प्रति प्रतीक में उत्पन्न किया जा सकता है।

जटिलता सारांश (Complexity Summary):

समय (Time): प्रति प्रतीक $O(1)$ एमॉर्टाइज्ड (कॉनकेटेनेशन) या प्रति प्रतीक $O(n)$ (सक्सेसर रूल)।
स्थान (Space): $O(n)$ (पैरामीटर्स के रैखिक में)।

5. महत्व (Significance)

खुले प्रश्नों का समाधान: यह कार्य $k$ -multisets के लिए कुशल निर्माण की दीर्घकालिक समस्या को हल करता है, जो इस शोध पत्र से पहले केवल गैर-रचनात्मक अस्तित्व प्रमाणों (non-constructive existence proofs) तक सीमित थी।
व्यावहारिक दक्षता: $O(1)$ एमॉर्टाइज्ड टाइम कॉम्प्लेक्सिटी इन निर्माणों को बड़े पैमाने के अनुप्रयोगों के लिए व्यवहार्य बनाती है, जैसे कि प्रॉक्सिमिटी सेंसर नेटवर्क (जहाँ मल्टीसेट्स सेंसर डेटा वितरण का प्रतिनिधित्व करते हैं) और कॉम्बिनेटोरियल टेस्टिंग।
एल्गोरिद्मिक नवाचार: "ग्रैंडमामा" सीक्वेंस का विस्तार और बाउंडेड-वेट बाधाओं के लिए MSR का अनुप्रयोग, डी ब्रुइन सीक्वेंस जनरेशन के व्यापक क्षेत्र के लिए नए उपकरण प्रदान करता है।
कार्यान्वयन: लेखक उल्लेख करते हैं कि इन एल्गोरिदम के कार्यान्वयन debruijnsequence.org लाइब्रेरी में उपलब्ध हैं, जो अनुसंधान समुदाय द्वारा तत्काल अपनाने और सत्यापन की सुविधा प्रदान करते हैं।

संक्षेप में, यह शोध पत्र उन्नत स्ट्रिंग रिप्रेजेंटेशन और उन्नत साइकिल-जॉइनिंग तकनीकों का लाभ उठाकर $k$ -subsets और $k$ -multisets के लिए यूनिवर्सल साइकल के सैद्धांतिक अस्तित्व को व्यावहारिक, अत्यधिक कुशल एल्गोरिदम में सफलतापूर्वक बदल देता है।