संयोजन की गणना रैंक?

Question

मैं संयोजनों के एक सेट में प्रत्येक संयोजन के लिए कुछ मानों की पूर्व-गणना करना चाहता हूं। उदाहरण के लिए, जब 12 0 से 3 संख्या को चुनने, मैं हर एक के लिए कुछ मूल्य की गणना होगी:

>>> for n in choose(range(13), 3): 
    print n, foo(n) 

(0, 1, 2) 78 
(0, 1, 3) 4 
(0, 1, 4) 64 
(0, 1, 5) 33 
(0, 1, 6) 20 
(0, 1, 7) 64 
(0, 1, 8) 13 
(0, 1, 9) 24 
(0, 1, 10) 85 
(0, 1, 11) 13 
etc... 

मैं एक सरणी में इन मूल्यों को स्टोर करने के लिए इतना है कि संयोजन को देखते हुए, मैं गणना अपनी और प्राप्त कर सकते हैं चाहता हूँ महत्व। उदाहरण के लिए:

>>> a = [78, 4, 64, 33] 
>>> a[magic((0,1,2))] 
78 

magic क्या होगा?

प्रारंभ में मैंने इसे आकार 3 x 13 x 13 के 3-डी मैट्रिक्स के रूप में स्टोर करने के लिए सोचा था, इसलिए मैं इसे आसानी से इस तरह से अनुक्रमित कर सकता हूं। हालांकि यह 13 चुनने के लिए ठीक है, यह 13 चुनने के लिए बहुत अधिक ओवरहेड होगा।

मैं एक नियम का उपयोग नहीं करना चाहता क्योंकि आखिरकार यह कोड सी में होगा, और एक सरणी होगी वैसे भी अधिक कुशल।

अद्यतन: मुझे भी एक ही समस्या है, लेकिन पुनरावृत्ति के साथ संयोजन का उपयोग करना, इसलिए उन लोगों के रैंक को प्राप्त करने के बारे में कोई भी जवाब बहुत सराहना की जाएगी =)।

अद्यतन: इसे स्पष्ट करने के लिए, मैं अंतरिक्ष को संरक्षित करने की कोशिश कर रहा हूं। इनमें से प्रत्येक संयोजन वास्तव में कुछ जगह लेता है, चलो 2 किलोबाइट्स कहते हैं। अगर मैं 13x13x13 सरणी का उपयोग करना चाहता था, तो यह 4 मेगाबाइट होगा, जिसमें से मुझे केवल 572 किलोबाइट्स (13 चुनें 3) स्पॉट का उपयोग करना होगा।

Answer 1

यहां एक वैचारिक उत्तर और एक कोड है जो लेक्स ऑर्डरिंग कैसे काम करता है। (तो मुझे लगता है कि मेरा जवाब "मूर्ख" की तरह है, सिवाय इसके कि मुझे लगता है कि उसके पास बहुत कम विवरण हैं और उसके लिंक बहुत अधिक हैं।) मैंने आपके लिए एक फ़ंक्शन unchoose(n,S) लिखा है जो यह मानता है कि एस एक ऑर्डर किया गया सूची सबसेट है range(n)। विचार: या तो एस 0 है या यह नहीं है। यदि ऐसा होता है, तो 0 को हटाएं और शेष सबसेट के लिए अनुक्रमणिका की गणना करें। यदि ऐसा नहीं होता है, तो यह बाद binomial(n-1,k-1) सबसेट है कि 0.

def binomial(n,k): 
    if n < 0 or k < 0 or k > n: return 0 
    b = 1 
    for i in xrange(k): b = b*(n-i)/(i+1) 
    return b 

def unchoose(n,S): 
    k = len(S) 
    if k == 0 or k == n: return 0 
    j = S[0] 
    if k == 1: return j 
    S = [x-1 for x in S] 
    if not j: return unchoose(n-1,S[1:]) 
    return binomial(n-1,k-1)+unchoose(n-1,S) 

def choose(X,k): 
    n = len(X) 
    if k < 0 or k > n: return [] 
    if not k: return [[]] 
    if k == n: return [X] 
    return [X[:1] + S for S in choose(X[1:],k-1)] + choose(X[1:],k) 

(n,k) = (13,3) 
for S in choose(range(n),k): print unchoose(n,S),S 

अब शामिल आता है, यह भी सच है कि आप कैश या दोनों काम करता है, द्विपद और unchoose के हैश मान सकते हैं। और इसके बारे में क्या अच्छा है कि आप सब कुछ precomputing और कुछ भी precomputing के बीच समझौता कर सकते हैं। उदाहरण के लिए आप केवल len(S) <= 3 के लिए प्रीकंप्यूट कर सकते हैं।

आप अनचाहे को अनुकूलित भी कर सकते हैं ताकि यह S[0] > 0 पर लूप के साथ द्विपक्षीय गुणांक जोड़ सके, पूंछ रिकर्सन को कम करने और उपयोग करने के बजाय।

Answer 2

आप संयोजन की शब्दावली अनुक्रमणिका का उपयोग करने का प्रयास कर सकते हैं। शायद यह पृष्ठ मदद करेगा: http://saliu.com/bbs/messages/348.html

इस एमएसडीएन पृष्ठ में अधिक जानकारी है: Generating the mth Lexicographical Element of a Mathematical Combination।

में थोड़ा और अधिक विशिष्ट होना करने के लिए:

जब एक टपल के रूप में इलाज, आप कोषगत संयोजन आदेश कर सकते हैं।

तो (0,1,2) < (0,1,3) < (0,1,4) आदि

कहो आप के लिए n-1 संख्या 0 था और उन से बाहर k चुना ।

अब यदि पहला तत्व शून्य है, तो आप जानते हैं कि यह पहले एन -1 चयन के -1 में से एक है।

यदि पहला तत्व 1 है, तो यह अगले एन-2 में से एक है के -1 चुनें।

इस तरह आप लेक्सिकोग्राफिक ऑर्डरिंग में दिए गए संयोजन की सटीक स्थिति की पुनरावृत्ति गणना कर सकते हैं और इसका उपयोग अपने नंबर पर मैप करने के लिए कर सकते हैं।

यह रिवर्स में भी काम करता है और एमएसडीएन पृष्ठ बताता है कि यह कैसे करें।

Answer 3

परिणामों को संग्रहीत करने के लिए हैश तालिका का उपयोग करें। एक सभ्य हैश समारोह हो सकता है कुछ की तरह:

h(x) = (x1*p^(k - 1) + x2*p^(k - 2) + ... + xk*p^0) % pp

कहाँ x1 ... xk अपने संयोजन में नंबर दिए गए हैं और p और pp (उदाहरण के (0, 1, 2)x1 = 0, x2 = 1, x3 = 2 है के लिए) अभाज्य संख्या है।

तो आप Hash[h(0, 1, 2)] = 78 स्टोर करेंगे और फिर आप इसे वैसे ही पुनर्प्राप्त करेंगे।

नोट: हैश तालिका आकार pp आकार की एक सरणी है, न कि एक निर्देश।

Answer 4

मैं एक विशेष हैश तालिका का सुझाव दूंगा। संयोजन के लिए हैश मूल्यों के लिए अनन्य-या हैश होना चाहिए। मूल्यों के लिए हैश मूल रूप से यादृच्छिक बिट-पैटर्न हैं।

आप टकराव से निपटने के लिए तालिका को कोड कर सकते हैं, लेकिन यह एक न्यूनतम पूर्ण हैश योजना प्राप्त करने के लिए काफी आसान होना चाहिए - एक जहां दो तीन आइटम संयोजन समान हैश मान नहीं देते हैं, और जहां हैश आकार और तालिका आकार को न्यूनतम रखा जाता है।

यह मूल रूप से Zobrist hashing है - संयोजन के एक आइटम को जोड़ने या हटाने के रूप में "चाल" के बारे में सोचें।

संपादित

कारण एक हैश तालिका का उपयोग करने के लिए कि देखने प्रदर्शन हे (एन) जहां n संयोजन में आइटम्स की संख्या है (कोई टकराव कल्पना करते हुए) है। संयोजन में लेक्सिकोोग्राफिक इंडेक्स की गणना करना काफी धीमी है, आईआईआरसी।

नकारात्मक रूप से तालिका उत्पन्न करने के लिए ऊपर की ओर काम किया गया है।

Answer 5

अभी के लिए, मैं एक समझौता पहुँच गए हैं: मैं एक 13x13x13 सरणी जो सिर्फ संयोजन के सूचकांक का मानचित्रण, 13x13x13x2 बाइट्स = 4 किलोबाइट लेने (लघु ints का उपयोग) है, के साथ साथ सामान्य आकार (13 चुनें 5) * 2 किलोबाइट = 572 किलोबाइट्स, कुल 576 किलोबाइट्स के लिए। 4 मेगाबाइट से काफी बेहतर, और रैंक गणना से भी तेज़!

मैंने यह आंशिक रूप से कारण किया कि मुझे काम करने का मॉरन का जवाब नहीं मिल रहा था। इसके अलावा यह अधिक विस्तार योग्य है - मेरे पास एक ऐसा मामला है जहां मुझे पुनरावृत्ति के साथ संयोजन की आवश्यकता है, और मुझे अभी तक उन लोगों के रैंक की गणना करने का कोई तरीका नहीं मिला है।

Answer 6

जो आप चाहते हैं उसे combinadics कहा जाता है।यहाँ इस अवधारणा के मेरी कार्यान्वयन है, पायथन में:

def nthresh(k, idx): 
    """Finds the largest value m such that C(m, k) <= idx.""" 
    mk = k 
    while ncombs(mk, k) <= idx: 
    mk += 1 
    return mk - 1 


def idx_to_set(k, idx): 
    ret = [] 
    for i in range(k, 0, -1): 
    element = nthresh(i, idx) 
    ret.append(element) 
    idx -= ncombs(element, i) 
    return ret 


def set_to_idx(input): 
    ret = 0 
    for k, ck in enumerate(sorted(input)): 
    ret += ncombs(ck, k + 1) 
    return ret 

Answer 7

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

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

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

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

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

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

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

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

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