क्या ओ (1) में एम-वर्ण-लंबाई संयोजन के के-वें तत्व प्राप्त करना संभव है?

Question

क्या आप ओ (1) में एम-एलिमेंट संयोजन के के-वें तत्व प्राप्त करने के किसी भी तरीके से जानते हैं? अपेक्षित समाधान किसी भी इनपुट डेटा और किसी भी एम मान के लिए काम करना चाहिए।

मुझे (अजगर कोड) उदाहरण के द्वारा इस समस्या के बारे में बताएं:

>>> import itertools 
>>> data = ['a', 'b', 'c', 'd'] 
>>> k = 2 
>>> m = 3 
>>> result = [''.join(el) for el in itertools.combinations(data, m)] 
>>> print result 
['abc', 'abd', 'acd', 'bcd'] 
>>> print result[k-1] 
abd 

एक दिया डेटा k- वां (इस उदाहरण में 2-nd) एम-तत्व संयोजन के तत्व के लिए अब्द है। क्या यह संपूर्ण संयोजन सूची बनाने के बिना उस मान (abd) के लिए संभव है?

मैं पूछ रहा हूं क्योंकि मेरे पास ~ 1,000,000 वर्णों का डेटा है और के-वें तत्व प्राप्त करने के लिए पूर्ण एम-वर्ण-लंबाई संयोजन सूची बनाना असंभव है।

समाधान छद्म कोड हो सकता है, या इस समस्या का वर्णन करने वाले पृष्ठ को लिंक (दुर्भाग्य से, मुझे एक नहीं मिला)।

धन्यवाद!

Answer 1

नहीं जरूरी हे (1), लेकिन अगले बहुत तेजी से किया जाना चाहिए:

मूल संयोजन एल्गोरिथ्म लें:

def combinations(elems, m): 
    #The k-th element depends on what order you use for 
    #the combinations. Assuming it looks something like this... 
    if m == 0: 
     return [[]] 
    else: 
     combs = [] 
     for e in elems: 
      combs += combinations(remove(e,elems), m-1) 

n प्रारंभिक तत्वों और m संयोजन लंबाई के लिए, हम है n!/(n-m)!m! कुल संयोजन । हम अपने वांछित संयोजन के लिए सीधे छोड़ इस तथ्य का उपयोग कर सकते हैं:

def kth_comb(elems, m, k): 
    #High level pseudo code 
    #Untested and probably full of errors 
    if m == 0: 
     return [] 
    else: 
     combs_per_set = ncombs(len(elems) - 1, m-1) 
     i = k/combs_per_set 
     k = k % combs_per_set 
     x = elems[i] 
     return x + kth_comb(remove(x,elems), m-1, k) 

Answer 2

पहले n तत्वों

की राशि के साथ r = !n/(!m*!(n-m)) गणना

तो मंजिल (आर/ट) परिणाम में पहला तत्व के सूचकांक है ,

इसे हटाने (बाईं ओर निम्नलिखित सब कुछ बदलाव)

करते m--, n-- और कश्मीर = r% कश्मीर

और दोहराने जब तक मीटर 0 (संकेत जब कश्मीर 0 केवल परिणाम के लिए निम्न वर्ण कॉपी है)

Answer 3

http://en.wikipedia.org/wiki/Permutation#Numbering_permutations

मूल रूप से है, भाज्य संख्या प्रणाली में सूचकांक व्यक्त करते हैं, और मूल अनुक्रम से एक चयन के रूप में अपने अंकों का उपयोग (स्थानापन्न के बिना)।

Answer 4

मैंने द्विपक्षीय गुणांक के साथ काम करने के लिए सामान्य कार्यों को संभालने के लिए एक कक्षा लिखी है, जो आपकी समस्या का सामना करने वाली समस्या का प्रकार है। यह निम्न कार्य करता है:

1. किसी भी एन के लिए एक अच्छा प्रारूप में सभी के-इंडेक्स आउटपुट को किसी फ़ाइल को के लिए चुनें। के-इंडेक्स को अधिक वर्णनात्मक तारों या अक्षरों के साथ प्रतिस्थापित किया जा सकता है। यह विधि इस प्रकार की समस्या को काफी तुच्छ हल करती है।

2. क्रमबद्ध द्विपदीय गुणांक तालिका में एंट्री के उचित सूचकांक में के-इंडेक्स को परिवर्तित करता है। यह तकनीक पुरानी प्रकाशित तकनीकों की तुलना में बहुत तेज है जो पुनरावृत्ति पर भरोसा करती है। यह पास्कल के त्रिभुज में अंतर्निहित गणितीय संपत्ति का उपयोग करके करता है। मेरे पेपर इस बारे में बात करते हैं।मेरा मानना ​​है कि मैं इस तकनीक को खोजने और प्रकाशित करने वाला पहला व्यक्ति हूं, लेकिन मैं गलत हो सकता हूं।

3. इंडेक्स को एक क्रमबद्ध बिनोमियल गुणांक तालिका में संबंधित के-इंडेक्स में परिवर्तित करता है। मेरा मानना ​​है कि यह भी अन्य प्रकाशित तकनीकों की तुलना में तेज़ है।

4. द्विपक्षीय गुणांक की गणना करने के लिए Mark Dominus विधि का उपयोग करता है, जो अतिप्रवाह होने की संभावना कम है और बड़ी संख्या में काम करता है।

5. कक्षा .NET C# में लिखा गया है और एक सामान्य सूची का उपयोग करके समस्या से संबंधित वस्तुओं (यदि कोई है) को प्रबंधित करने का एक तरीका प्रदान करता है। इस वर्ग के निर्माता को इटटेबल नामक एक बूल वैल्यू लेता है, जब सत्य ऑब्जेक्ट्स को प्रबंधित करने के लिए एक सामान्य सूची बनायेगा। यदि यह मान गलत है, तो यह तालिका नहीं बनाएगा। उपरोक्त 4 विधियों को करने के लिए तालिका को बनाने की आवश्यकता नहीं है। तालिका तक पहुंचने के लिए एक्सेसर विधियां प्रदान की जाती हैं।

6. एक संबंधित टेस्ट क्लास है जो दिखाती है कि कक्षा और उसके तरीकों का उपयोग कैसे करें। इसका व्यापक रूप से 2 मामलों के साथ परीक्षण किया गया है और कोई ज्ञात बग नहीं है।

इस कक्षा के बारे में पढ़ने और कोड डाउनलोड करने के लिए, Tablizing The Binomial Coeffieicent देखें।

इस कक्षा को जावा, पायथन या सी ++ में परिवर्तित करना मुश्किल नहीं होना चाहिए।