अजगर itertools.product के साथ एक सूची बनाने के?

Question

मैं श्रेणियों की सूची से itertools के साथ एक सूची बना रहा हूं, अब तक मैं इस है:

start_list = [xrange(0,201,1),xrange(0,201,2),xrange(0,201,5),xrange(0,201,10),xrange(0,201,20),xrange(0,201,50),xrange(0,201,100),xrange(0,201,200)] 

अब, मुझे पता है कि अगर मैं इस अगली पंक्ति को चलाने के लिए प्रयास करने के लिए थे कि यह मेरे अजगर दुभाषिया मार डालेगा :

next_list = list(itertools.product(*start_list)) 

क्या मैं सोच रहा हूँ है यह एक तर्क है कि इसके आइटम की राशि के लिए प्रत्येक टपल की जाँच करता है, में डालने के लिए संभव हो जाएगा और केवल उन्हें next_list में डालता है, तो बराबर एक निश्चित राशि के लिए?

हो सकता है कि कुछ की तरह:

next_list = list(itertools.product(*start_list,sum(tuples)=200)) 

मैं जानता हूँ कि यह सही नहीं है और मैं फिर से सोचने के लिए जिस तरह से मैं इस बारे में जा रहा हूँ शुरू करने की आवश्यकता हो सकती है। जनरेटर में start_list की श्रेणियां एक और सूची बनाने के लिए बहुत अधिक हो जाएंगी?

Answer 1

बेहतर

सिर्फ एक सूची का उपयोग करने समझ

new_list = [item for item in itertools.product(*start_list) if sum(item) == 200] 

Answer 2

उपयोग करें:

next_list = सूची (itertools.product (में आइटम के लिए आइटम * START_LIST) यदि राशि (आइटम) == 200)

Answer 3

Solution  Runtime   Fn calls   Lines of Code 
-------- ---------- ------------------------ ------------- 
gnibbler 2942.627 s 1473155845 (1.5 billion)   1 
me_A   16.639 s  28770812 (29 million)   5 
me_B   0.452 s  774005 (.8 million)   43 

---

समाधान me_A:

import itertools 

def good_combos(basis, addto): 
    good_sums = set(addto-b for b in basis[0]) 
    return ([addto-sum(items)]+list(items) for items in itertools.product(*basis[1:]) if sum(items) in good_sums) 

next_list = list(good_combos(start_list, 200)) 

ध्यान दें कि इस बहुत तेजी से अगर आप इसे सबसे लंबे समय तक सूची पहले पारित हो सकता है।

यह समाधान एक सेट देखने के साथ यात्रा में से एक स्तर को बदल देता है; 200 वस्तुओं वाली आपकी सबसे लंबी सूची के साथ, यह आश्चर्य की बात नहीं है कि यह लगभग 200 गुना तेज है।

---

समाधान me_B: अधिक सामान्य आधार पर हालांकि - - प्रत्येक सूची किसी भी लाभ उठाने की यह वंचित, दोनों 0 और addto शामिल

import itertools 
from bisect import bisect_left, bisect_right 

def good_combos(addto=0, *args): 
    """ 
    Generate all combinations of items from a list of lists, 
    taking one item from each list, such that sum(items) == addto. 

    Items will only be used if they are in 0..addto 

    For speed, try to arrange the lists in ascending order by length. 
    """ 
    if len(args) == 0:       # no lists passed? 
     return [] 

    args = [sorted(set(arg)) for arg in args] # remove duplicate items and sort lists in ascending order 
    args = do_min_max(args, addto)    # use minmax checking to further cull lists 

    if any(len(arg)==0 for arg in args):  # at least one list no longer has any valid items? 
     return [] 

    lastarg = set(args[-1]) 
    return gen_good_combos(args, lastarg, addto) 

def do_min_max(args, addto, no_negatives=True): 
    """ 
    Given 
     args   a list of sorted lists of integers 
     addto   target value to be found as the sum of one item from each list 
     no_negatives if True, restrict values to 0..addto 

    Successively apply min/max analysis to prune the possible values in each list 

    Returns the reduced lists 
    """ 
    minsum = sum(arg[0] for arg in args) 
    maxsum = sum(arg[-1] for arg in args) 

    dirty = True 
    while dirty: 
     dirty = False 
     for i,arg in enumerate(args): 
      # find lowest allowable value for this arg 
      minval = addto - maxsum + arg[-1] 
      if no_negatives and minval < 0: minval = 0 
      oldmin = arg[0] 
      # find highest allowable value for this arg 
      maxval = addto - minsum + arg[0] 
      if no_negatives and maxval > addto: maxval = addto 
      oldmax = arg[-1] 

      if minval > oldmin or maxval < oldmax: 
       # prune the arg 
       args[i] = arg = arg[bisect_left(arg,minval):bisect_right(arg,maxval)] 
       minsum += arg[0] - oldmin 
       maxsum += arg[-1] - oldmax 
       dirty = True 
    return args 

def gen_good_combos(args, lastarg, addto): 
    if len(args) > 1: 
     vals,args = args[0],args[1:] 
     minval = addto - sum(arg[-1] for arg in args) 
     maxval = addto - sum(arg[0] for arg in args) 
     for v in vals[bisect_left(vals,minval):bisect_right(vals,maxval)]: 
      for post in gen_good_combos(args, lastarg, addto-v): 
       yield [v]+post 
    else: 
     if addto in lastarg: 
      yield [addto] 

basis = reversed(start_list) # more efficient to put longer params at end 
new_list = list(good_combos(200, *basis)) 

do_min_max() वास्तव में अपने डेटा सेट पर बात की पूर्ति नहीं कर सकते हैं डेटा यह समस्या आकार को बहुत कम कर सकता है।

यहां बचत क्रमिक यात्रा (पेड़ छंटाई) के प्रत्येक स्तर पर माना जाता आइटम्स की संख्या को कम करने में पाए जाते हैं।