在给定范围内寻找一个列表的所有可能子列表的有效& Pythonic方法，以及在对其中的所有元素进行多重处理之后找到最小乘积的方法？

Question

，我已经完成了这两件事。

1. 查找给定范围(i ,j)中列表的所有可能子列表。

A= 44、55、66、77、88、99、11、22、33设，i=2和j=4

然后，给定范围内的列表"A"的可能子列表(2,4)是：

66、66、77、66、77、88、77、77、88

1. 并且，在对子列表中的所有元素进行多重处理之后，得到的产品的最小值：

因此，将上述子列表中的所有元素相乘后的结果列表将变成

X= 66,5082,447216，77,6776，88

现在，上面列表的最小值，即min(X) i- 66

我的代码：

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)

我的问题：

对于更大的列表和更大的范围，这段代码需要更多的时间来执行！

有没有任何可能的"Pythonic“方法来降低上述代码的时间复杂度？

提前谢谢！

编辑:

明白了。但是，如果有多个这样的子列表具有相同的最小乘积，

1. 我需要最长的子列表范围(i,j)
2. 如果仍然有多个子列表具有相同的“最长子范围”，我需要打印具有最低开始索引的子间隔。

考虑一下这个列表A = [2, 22, 10, 12, 2] (如果是(i,j) = (0,4) )。

有一条领带。Min product = 2有两种可能性，'(0,0)' and '(4,4)'。

两个子列表范围=0 [ (0-0) and (4-4) ]

在这种情况下，我需要print (minproduct, [sublist-range]) = 2, [0,0]

尝试使用字典，它工作一些输入，但不是所有的！如何“高效”地做到这一点？

谢谢！

Answer 1

首先，给定列表和索引范围，我们可以得到子列表A[i : j + 1]

[66, 77, 88]

对于正整数a和b，a * b不小于a或b。所以你不需要做乘法，两个或更多元素的乘积不可能有更小的结果。此列表的最小值是所有乘积结果的最小值。

结果是：

min(A[i : j + 1])

Answer 2

要生成子列表，它就像列表理解中的两个嵌套for循环一样简单：

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

示例：

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

为了找到最低的产品：

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

(从prod导入numpy，或将其定义为def prod(x): return reduce(lambda i,j:i*j,x))

Answer 3

接受的答案对于所有的正整数都是正确的，因为你不能把最小的元素乘以任何数，得到一个较小的结果。如果所有的切片都大于长度1，这可能更有意义。

如果要计算它，则可以使用itertools.islice获取每个切片，并使用生成器表达式获取最小值：

from itertools import islice
from operator import mul

print(min(reduce(mul, islice(A, n, k + 1), 1)
          for n in range(i, j + 1) for k in range(n, j + 1)))

66

如果对于i=0和j=4，您认为(44, 55, 66, 88)是一个合法的片，那么您需要使用itertools.combinations。