Numpy - समूह डेटा राशि में महत्व देता

मैं मूल्यों की एक सरणी है कहते हैं:Numpy - समूह डेटा राशि में महत्व देता

a = np.array([1,5,4,2,4,3,1,2,4])

और तीन 'योग' मान:

b = 10 
c = 9 
d = 7

वहाँ समूह के लिए एक रास्ता a में मूल्यों में है सेट के समूह जहां मूल्य बराबर बी, सी और डी के साथ गठबंधन करते हैं? उदाहरण के लिए:

b: [5,2,3] 
c: [4,4,1] 
d: [4,2,1] 

b: [5,4,1] 
c: [2,4,3] 
d: [4,2,1] 

b: [4,2,4] 
c: [5,4] 
d: [1,1,2,3]

नोट b, c और d की राशि एक ही (== 26) रहना चाहिए। शायद इस ऑपरेशन का नाम पहले से ही है?

स्रोत

2013-10-02 atomh33ls

ऐसा लगता है कि आप "knapsack समस्या" (या इसके संस्करण) को हल करने की कोशिश कर रहे हैं: http://en.wikipedia.org/wiki/Knapsack_problem –

इसी तरह हाँ, मैं इसे "एकाधिक knapsack" कहूंगा मुसीबत"। जैसे आप अपनी सामग्री को तीन knapsacks में पैक कर सकते हैं (जहां लागत कोई मुद्दा नहीं है)। – atomh33ls

तो यह एक खोज समस्या है, न कि संख्यात्मक (numpy) एक। और अधिकांश खोज समस्याओं के साथ, एक ब्रूट फोर्स सॉल्यूशन है, और विभिन्न रणनीतियों (अक्सर हेरिस्टिक) मृतक शाखाओं को छीनने के लिए। – hpaulj

यहाँ एक अनुभवहीन कार्यान्वयन है itertools का उपयोग कर

from itertools import chain, combinations 

def group(n, iterable): 
    s = list(iterable) 
    return [c for c in chain.from_iterable(combinations(s, r) 
              for r in range(len(s)+1)) 
      if sum(c) == n]

group(5, range(5))

पैदावार

[(1, 4), (2, 3), (0, 1, 4), (0, 2, 3)]

ध्यान दें, यह शायद बड़े सूचियों के लिए बहुत धीमी गति से होगा, क्योंकि हम अनिवार्य रूप से निर्माण और छानने रहे हैं उस सूची के पावर सेट के माध्यम से।

आप और के लिए

sum_vals = [10, 9, 7] 
a = [1, 5, 4, 2, 4, 3, 1, 2, 4] 

map(lambda x: group(x, a), sum_vals)

इस इस्तेमाल कर सकते हैं तो उन्हें zip एक साथ।

स्रोत

2013-10-02 15:00:45 wflynny

यह अंतर्निहित शर्त को पूरा नहीं करता है कि 'a' में प्रत्येक मान को केवल एक समूह में रखा जा सकता है। – askewchan

@askewchan, आप सही हैं। लेकिन मुझे लगता है कि यह एक अच्छा प्रारंभिक बिंदु हो सकता है। मैं 'np.unique (समूह (बी, ए)) 'और फिर समूह (सी, ए)' और 'समूह (डी, ए)' के आउटपुट के साथ परीक्षण के बाद किसी भी तरह काटने के साथ टकरा रहा हूं। हालांकि अभी तक सफल नहीं हुआ है। – atomh33ls

हां, इसमें सभी की कमी है अंत में एक फ़िल्टर है जो जांचता है कि दो संग्रह बराबर हैं। 'np.unique' पर्याप्त नहीं है क्योंकि ऑर्डर कोई फर्क नहीं पड़ता, प्रत्येक प्रविष्टि की गणना करता है। आप उनकी 'बकाया राशि' की तुलना कर सकते हैं। – askewchan

Numpy - समूह डेटा राशि में महत्व देता

उत्तर

संबंधित मुद्दे