python - Efficient & Pythonic way of finding all possible sublists of a list in given range and the minimum product after multipying all elements in them? -


i've achived these 2 things.

  1. find possible sublists of list in given range (i ,j).

    a = [ 44, 55, 66, 77, 88, 99, 11, 22, 33 ]  let, = 2 , j = 4 

    then, possible sublists of list "a" in given range (2,4) :

    [66], [66,77], [66,77,88], [77], [77,88], [88] 
  2. and, minimum of resultant product after multipying elements of sublists:

    so, resultant list after multiplying elements in above sublists become

    x = [66, 5082, 447216, 77, 6776, 88]`     

    now, minimum of above list, min(x) i.e 66

my code:

i, j = 2, 4 = [ 44, 55, 66, 77, 88, 99, 11, 22, 33 ]  o, p = i, mini = a[o] while o <= j , p <= j:     if o == p:         mini = min(mini, reduce(lambda x, y: x * y, [a[o]]))     else:         mini = min(mini, reduce(lambda x, y: x * y, a[o:p + 1]))     p += 1     if p > j:         o += 1         p = o print(mini) 

my question:

this code taking more time executed larger lists , larger ranges !
there possible "pythonic" way of reducing time complexity of above code ?

in advance !

edit :

got it. but, if there more 1 such possible sublist same minimum product,

  1. i need longest sub list range (i,j)
  2. if there still more 1 sublists same "longest sub range", need print sub-interval has lowest start index.


consider list a = [2, 22, 10, 12, 2] if (i,j) = (0,4).
there tie. min product = 2 2 possibilities '(0,0)' , '(4,4)' .
both sub list range = 0 [ (0-0) , (4-4) ]
in case need print (minproduct, [sublist-range]) = 2, [0,0]

tried using dictionaries, works inputs not ! how 'efficiently' ?
thank !

first, given list , index range, can sublist a[i : j + 1]

[66, 77, 88] 

for positive integers a , b, a * b no less a or b. don't need multiplying, it's not possible multiplying of 2 or more elements has smaller result. minimum of list is minimum of multiplying results.

so result is:

min(a[i : j + 1]) 

Comments

Popular posts from this blog

facebook - android ACTION_SEND to share with specific application only -

python - Creating a new virtualenv gives a permissions error -

javascript - cocos2d-js draw circle not instantly -