एक सीमा सूची से सभी संभावित संयोजनों को एक सीमा

Question

के तहत जेनरेट करें, मुझे इसे पायथन में करने की आवश्यकता है। एक दी गई सूची एल है, इसमें 5000 से अधिक पूर्णांक तत्व हो सकते हैं। संख्याओं की संख्या, 20000 या उच्च हो सकती है। उत्पादन सूची, तरह से उठाया सभी 2 संख्या के संभावित रकम होना चाहिए,

l=[1,2,3,4,5,6,7,8,9] 
output 
1+1,1+2,1+3,1+4,1+5,1+6........... 
2+2,2+3,2+4....... 
......... 
....... 

2,3,4,5,6... like that 

मैं, इस कोड का उपयोग कर रहा हूँ अब के लिए ऐसा करने से, लेकिन यह धीमी है

l=listgen() 
p=[] 
for i in range(0,len(l)): 
    for j in range(i,len(l)): 
     k=l[i]+l[j] 
     if k not in p: 
      p.append(k) 
p.sort 
print(p) 

listgen() वह इनपुट है जो इनपुट सूची उत्पन्न करता है।

Answer 1

कुछ पुराने ढंग का अनुकूलन आप तेजी से कोड छोरों के लिए कई के साथ सूची comprehensions से grok में आसान है मिल सकता है: एक अतिरिक्त बोनस के रूप में

def sums(lst, limit): # prevent global lookups by using a function 
    res = set()   # set membership testing is much faster than lists 
    res_add = res.add # cache add method 
    for i, first in enumerate(lst): # get index and item at the same time 
     for second in lst[i:]:  # one copy operation saves n index ops. 
      res_add(first + second) # prevent creation/lookup of extra local temporary 
    return sorted([x for x in res if x < limit]) 

print sums(listgen(), 20000) 

, इस संस्करण psyco, cython के साथ खूबसूरती से अनुकूलित करेंगे , आदि।

अद्यतन: जब अन्य सुझावों (सीमा (5000) के साथ listgen की जगह को यह तुलना, मैं:।

mine:  1.30 secs 
WolframH: 2.65 secs 
lazyr:  1.54 secs (estimate based on OPs timings -- I don't have Python 2.7 handy) 

Answer 2

संपादित करें: थिबॉर्न का कहना है कि उनके पास सबसे कुशल समाधान है, और मेरे अपने परीक्षण सहमत हैं, हालांकि मैंने अपने प्रदर्शन में थोड़ा सुधार किया है। उनका कोड पायथन संस्करण पर भी कम निर्भर है और ऐसा लगता है कि इष्टतमकरण के संबंध में बहुत अच्छी तरह से सोचा और समझाया गया है। आपको उसका जवाब स्वीकार करना चाहिए (और उसे उपरोक्त देना)।

itertools.combinations_with_replacement (पायथन 2.7 में जोड़ा गया) का उपयोग करें, और pset बनाएं।

तुम सिर्फ इतना है कि p एक set है, यह एक बड़ा फर्क होता कि आपके कोड में छोटे परिवर्तन की एक जोड़ी बनाते हैं:

def sums(lst, limit): 
    from itertools import combinations_with_replacement 
    p = set(x + y for x, y in combinations_with_replacement(listgen(), 2)) 
    return sorted([x for x in p if x < limit]) 

आपका कोड इस लाइन की वजह से धीमी है

L = listgen() 
p = set() 
for i in range(0, len(L)): 
    for j in range(i, len(L)): 
     p.add(L[i] + L[j]) 
print(sorted(p)) 

वैसे, अपने उदाहरण में इस लाइन

p.sort 

का कोई प्रभाव नहीं है। आपको वास्तव में इसे निष्पादित करने के लिए एक विधि को कॉल करना होगा, जैसे:

p.sort() 

Answer 3

संपादित करें: सीमा शामिल है (जो ओपी के कोड में नहीं था)।

a = set(x + y for x in l for y in l) 
print(sorted(x for x in a if x < limit)) 

भी यही कारण है कि एल्गोरिथ्म की जटिलता (तुम्हारा संभावित O (n^4) किसी सूची में सदस्यता परीक्षण की वजह से है) कम कर देता है।

Answer 4

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

Answer 5

यदि इनपुट सूची सॉर्ट की गई है, तो आप सीमा तक पहुंचने पर भीतरी पाश से बाहर निकल सकते हैं। इसके अलावा, p एक सेट बनाएं।

lst=listgen() 
lst.sort() 
p=set() 
for i in range(0,len(lst)): 
    for j in range(i,len(lst)): 
     k=lst[i]+lst[j] 
     if k > limit: 
      break 
     p.add(k) 
p = sorted(p) 
print(p) 

Answer 6

आप इस के लिए "NumPy" इस्तेमाल कर सकते हैं यह आप निश्चित रूप से देता है आवश्यक प्रदर्शन:

import numpy as np 

data = np.arange(5000) 
limit = 20000 
result = np.zeros(0,dtype='i4') 
for i in data: 
    result = np.concatenate((result,data[i]+data[i:])) 
    if len(result) >= limit: break 
result = result[:limit] 

संपादित करें: मैं सिर्फ महसूस किया कि सीमा पर है तत्वों की संख्या पर योग और नहीं। फिर कोड पढ़ना चाहिए:

EDIT2: और तार्किक त्रुटियां मिलीं। मेरे को सही सुझाव है:

for idx, x in np.ndenumerate(data): 
    result = np.concatenate((result,x+data[idx[0]:])) 
    if x + data[-1] >= limit: break 
result = result[result <= limit]