कुशल आइटम बिनिंग एल्गोरिदम (itertools/numpy)

Question

मुझे लगता है कि यह एक आम संयोजन समस्या है, लेकिन मुझे इसके बारे में कोई नाम या इसके बारे में कोई सामग्री नहीं मिल रही है। मैं इसे पायथन और numpy में कर रहा हूँ, लेकिन अगर इसके लिए एक तेज मैट्रिक्स विधि है, तो मैं शायद अनुवाद कर सकते हैं।

असल में, n आइटम को देखते हुए, मैं उन्हें मीटर डिब्बे में डाल करने के लिए सभी तरह से उत्पन्न करने के लिए की जरूरत है। उदाहरण के तौर पर, 3 डिब्बे में 4 आइटमों को बांधने से [(4, 0, 0), (3, 1, 0), (3, 0, 1), (2, 2, 0), (2, 1, 1), ...] कुछ मिलता है। यह एक निश्चित कुल के साथ एक उत्पाद है।

itertools के साथ इसे कार्यान्वित करना सरल है।

import itertools 

def fixed_total_product(bins, num_items): 
""" Return iterator of all item binning possibilities. """ 
return itertools.ifilter(lambda combo: sum(combo) == num_items, 
         itertools.product(xrange(num_items + 1), repeat=bins)) 

दुर्भाग्य से, मुझे लगता है कि लूप में बाद की गणना करना अक्षम होगा। इसके साथ 2 डी numpy सरणी के रूप में काम करना तेजी से बाद में होगा, लेकिन मैं इसके साथ एक सरणी बनाने के लिए एक कुशल तरीका नहीं समझ सकता। मैं ifilter परिणाम पर पुन: प्रयास कर सकता हूं, संभावनाओं की एक सूची बना सकता हूं, और सरणी बनाने के लिए इसका उपयोग कर सकता हूं, लेकिन यह एक विशाल अपशिष्ट की तरह लगता है।

मुझे लगता है कि ऐसा करने का सबसे अच्छा तरीका यह है कि "सबकुछ रास्ता" बनाना है, लेकिन मुझे यकीन नहीं है कि यह कैसे करें। स्टैक ओवरफ्लो पर एक त्वरित उत्पाद कार्यान्वयन है: Using numpy to build an array of all combinations of two arrays। मुझे लगता है कि आप इसे केवल सही उत्पादों के साथ आउटपुट उत्पादों में संशोधित कर सकते हैं। सरणी का आकार होना चाहिए ((एम -1) + एन) एन चुनें, क्योंकि एम -1 बिन सीमाएं हैं।

कोई विचार? बेंचमार्क बहुत सराहना की, लेकिन आवश्यक नहीं है।

Answer 1

रिकॉर्शन सी (एन, के) = सी (एन -1, के -1) + सी (एन -1, के -1)) के आधार पर, numpy ऑपरेशंस का उपयोग करके याद किया गया।

import numpy as np 

def binnings(n, k, cache={}): 
    if n == 0: 
     return np.zeros((1, k)) 
    if k == 0: 
     return np.empty((0, 0)) 
    args = (n, k) 
    if args in cache: 
     return cache[args] 
    a = binnings(n - 1, k, cache) 
    a1 = a + (np.arange(k) == 0) 
    b = binnings(n, k - 1, cache) 
    b1 = np.hstack((np.zeros((b.shape[0], 1)), b)) 
    result = np.vstack((a1, b1)) 
    cache[args] = result 
    return result 

if __name__ == '__main__': 
    import timeit 
    print timeit.timeit('binnings(20, 5, {})', setup='from __main__ import binnings', number=1) 

सेकंड में समय के लिए (20, 5):

0.0129251480103 

Answer 2

शायद numpy में कुछ अलग चाल का उपयोग कर एक तेज़ तरीका है। numpy.indicies वह जगह है जहां आप शुरू करना चाहते हैं। एक बार जब आप rollaxis के साथ गठबंधन करते हैं, तो यह अनिवार्य रूप से itertools.product के बराबर है। स्वेन मार्नैच का जवाब in this question इसका एक उत्कृष्ट उदाहरण है (हालांकि, आप अपने अंतिम उदाहरण में एक मामूली त्रुटि है। यह numpy.indices((len(some_list) + 1), * some_length... होना चाहिए)

हालांकि, ऐसा कुछ करने के लिए, यह होने की संभावना है itertools का उपयोग कर अधिक पठनीय।

numpy.fromiter चीजों को स्पष्ट रूप से परिवर्तित करने की तुलना में थोड़ा तेज़ है, खासकर अगर आप इसे इटरेटर में आइटमों की संख्या का गिनती देते हैं। मुख्य लाभ यह है कि काफी कम स्मृति का उपयोग होता है, जो बड़े इटरेटर्स के मामले में बहुत उपयोगी हो सकता है।

import itertools 
import numpy as np 
import scipy.special 


def fixed_total_product(bins, num_items): 
    return itertools.ifilter(lambda combo: sum(combo) == num_items, 
      itertools.product(xrange(num_items + 1), repeat=bins)) 

def fixed_total_product_fromiter(bins, num_items): 
    size = scipy.special.binom(bins - 1 + num_items, num_items) 
    combinations = fixed_total_product(bins, num_items) 
    indicies = (idx for row in combinations for idx in row) 
    arr = np.fromiter(indicies, count=bins * int(size), dtype=np.int) 
    return arr.reshape(-1, bins) 

def fixed_total_product_fromlist(bins, num_items): 
    return np.array(list(fixed_total_product(bins, num_items)), dtype=np.int) 

def fixed_total_product_numpy(bins, num_items): 
    arr = np.rollaxis(np.indices((num_items + 1,) * bins), 0, bins + 1) 
    arr = arr.reshape(-1, bins) 
    arr = np.arange(num_items + 1)[arr] 
    sums = arr.sum(axis=1) 
    return arr[sums == num_items] 

m, n = 5, 20 

if __name__ == '__main__': 
    import timeit 
    list_time = timeit.timeit('fixed_total_product_fromlist(m, n)', 
      setup='from __main__ import fixed_total_product_fromlist, m, n', 
      number=1) 
    iter_time = timeit.timeit('fixed_total_product_fromiter(m, n)', 
      setup='from __main__ import fixed_total_product_fromiter, m, n', 
      number=1) 
    numpy_time = timeit.timeit('fixed_total_product_numpy(m, n)', 
      setup='from __main__ import fixed_total_product_numpy, m, n', 
      number=1) 

    print 'All combinations of {0} items drawn from a set of {1} items...'.format(m,n) 
    print ' Converting to a list and then an array: {0} sec'.format(list_time) 
    print ' Using fromiter: {0} sec'.format(iter_time) 
    print ' Using numpy.indices: {0} sec'.format(numpy_time) 

समय के लिए के रूप में::

यहाँ कुछ दोनों numpy.indices चाल और एक numpy सरणी इटरेटर परिवर्तित करने के विभिन्न तरीकों का उपयोग कर उदाहरण हैं

All combinations of 5 items drawn from a set of 20 items... 
    Converting to a list and then an array: 2.75901389122 sec 
    Using fromiter: 2.10619592667 sec 
    Using numpy.indices: 1.44955015182 sec 

आप कि कोई भी ध्यान देंगे वे विशेष रूप से तेज़ हैं।

आप एक ब्रूट-फोर्स एल्गोरिदम का उपयोग कर रहे हैं (सभी संभावित संयोजन उत्पन्न करें और फिर उन्हें फ़िल्टर करें), और मैं इसे यहां numpy- आधारित उदाहरण में कॉपी कर रहा हूं।

शायद ऐसा करने के लिए एक और अधिक प्रभावी तरीका है! हालांकि, मैं किसी भी माध्यम से सीएस या गणित व्यक्ति नहीं हूं, इसलिए मुझे नहीं पता कि सभी संभव संयोजनों को उत्पन्न किए बिना ऐसा करने के लिए एक प्रसिद्ध एल्गोरिदम है ...

शुभकामनाएं, किसी भी दर पर !