I've achived these two things.
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]
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,
(i,j)
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 !
adjective. If something or someone is efficient, they are able to do tasks successfully, without wasting time or energy.
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.
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.
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])
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)
)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With