Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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 two things.

  1. Find all possible sublists of a list in given range (i ,j).

    A = [ 44, 55, 66, 77, 88, 99, 11, 22, 33 ] 
    Let, i = 2 and j = 4
    

    Then, Possible sublists of the list "A" in the given range (2,4) is :

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

    So, the resultant list after multiplying all the elements in the above sublists will become

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

    Now, the minimum of the above list, which is min(X) i.e 66

My Code:

i, j = 2, 4
A = [ 44, 55, 66, 77, 88, 99, 11, 22, 33 ] 
O, P = i, i
mini = A[O]
while O <= j and 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 is taking more time to get executed for the Larger Lists and Larger Ranges !
Is there any possible "Pythonic" way of reducing the time complexity of the above code ?

Thanks in advance !

EDIT :

Got it. But, If there is more than one such possible sublist with the same minimum product,

  1. I need the longest sub list range (i,j)
  2. If there are still more than one sublists with the same "longest sub range", I need to print the sub-interval which has the lowest start index.


Consider this list A = [2, 22, 10, 12, 2] if (i,j) = (0,4).
There is a tie. Min product = 2 with two possibilities '(0,0)' and '(4,4)' .
Both sub list range = 0 [ (0-0) and (4-4) ]
In this case i need to print (minproduct, [sublist-range]) = 2, [0,0]

Tried using dictionaries, It works for some inputs but not for all ! How to do this 'efficiently' ?
Thank you !

like image 812
sr1 Avatar asked Jun 13 '15 16:06

sr1


People also ask

What do you mean of efficient?

adjective. If something or someone is efficient, they are able to do tasks successfully, without wasting time or energy.

What is efficient and example?

working or operating quickly and effectively in an organized way: The city's transportation system is one of the most efficient in Europe. We need someone really efficient who can organize the office and make it run smoothly. Thesaurus: synonyms, antonyms, and examples.

How do you describe an efficient person?

performing or functioning in the best possible manner with the least waste of time and effort; having and using requisite knowledge, skill, and industry; competent; capable: a reliable, efficient assistant.


2 Answers

First, given the list and the index range, we can get the sublist A[i : j + 1]

[66, 77, 88]

For positive integers a and b, a * b is no less than a or b. So you don't need to do multiplying, it's not possible that multiplying of two or more elements has a smaller result. The minimum of this list is the minimum of all the multiplying results.

So the result is:

min(A[i : j + 1])
like image 181
Yu Hao Avatar answered Nov 07 '22 09:11

Yu Hao


For generating the sublists, it is as simple as two nested for loops in a list comprehension:

def sublists(l,i,j):
    return [l[m:n+1] for m in range(i,j+1) for n in range(m,j+1)]

example:

>>> sublists(A,2,4)
[[66], [66, 77], [66, 77, 88], [77], [77, 88], [88]]

For finding the minimum product:

>>> min(map(prod, sublists(A,2,4)))
66

(you import prod from numpy, or define it as def prod(x): return reduce(lambda i,j:i*j,x))

like image 39
fferri Avatar answered Nov 07 '22 09:11

fferri