在给定范围内查找列表的所有可能子列表的高效和 Pythonic 方法，以及将其中的所有元素相乘后的最小乘积？

Question

这两件事我都做到了

在给定范围 (i ,j) 中查找列表的所有可能子列表。
```
A = [ 44, 55, 66, 77, 88, 99, 11, 22, 33 ] 
Let, i = 2 and j = 4
```
那么，给定范围(2,4)中列表"A"的可能子列表是：
```
[66], [66,77], [66,77,88], [77], [77,88], [88]
```
并且，将子列表的所有元素相乘后的结果乘积的最小值：

因此，将上述子列表中的所有元素相乘后的结果列表将变为
```
X = [66, 5082, 447216, 77, 6776, 88]`    
```
现在，上面列表的最小值，即 min(X) 即 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" 方法来降低上述代码的时间复杂度？

提前致谢！

编辑：

知道了。但是，如果存在多个具有相同最小乘积的可能子列表，

我需要最长的子列表范围(i,j)
如果还有多个子列表具有相同的"longest sub range"，我需要打印具有最低起始索引的子区间。

如果 (i,j) = (0,4)，请考虑此列表 A = [2, 22, 10, 12, 2]。
有一条领带。 Min product = 2 有两种可能性 '(0,0)' and '(4,4)' 。
两个子列表范围 = 0 [ (0-0) and (4-4) ]
在这种情况下，我需要 print (minproduct, [sublist-range]) = 2, [0,0]

尝试使用字典，它适用于某些输入但不适用于所有输入！如何做到这一点 'efficiently' ？
谢谢！

Answer 1

看一看itertools.combinations()

https://docs.python.org/3/library/itertools.html#itertools.combinations

循环调用它传递子列表，另一个参数从 1 到子列表的长度不等。

肯定要"more time to get executed for the Larger Lists and Larger Ranges"，我觉得这是必然的。但可能比你的方法快得多。测量看看。

Answer 2

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

[66, 77, 88]

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

所以结果是：

min(A[i : j + 1])

Answer 3

为了生成子列表，它就像列表理解中的两个嵌套 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

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

Answer 4

#EDIT：快速解决方案：

min(A[i:j+1])

由于所有数字都是正整数，而你想求A[i:j+1]列表
所有可能子列表的最小乘积切片，它还将包含长度为 1 的子列表。所有此类子列表的最小乘积将是 A[i:j+1] 切片中最小的数字。

另一种解法：

当您需要查找子列表的最大乘积或者您需要A[i:j+1]列表切片的所有可能组合时，下面的方法将很有用。

我们将使用 itertools.combinations 来解决这个问题。我们可以分 3 个步骤完成。

第一步：获取列表的切片

my_list = A[i:j+1]

这将为我们提供要处理的切片。

my_list = A[2:5]
my_list
[66, 77, 88]

Step-2 生成所有可能的组合：

import itertools

my_combinations = []

for x in range(1, len(my_list)+1):
    my_combinations.extend(list(itertools.combinations(my_list,x)))

my_combinations
[(66,), (77,), (88,), (66, 77), (66, 88), (77, 88), (66, 77, 88)]

iterools.combinations returns r length subsequences of elements from the input iterable

因此，我们将使用它来生成长度为 1 到长度等于 my_list 的子序列。我们将得到一个元组列表，每个元素都是一个子序列。

第 3 步：查找所有可能组合的最小乘积

products_list = [reduce(lambda i,j:i*j, x) for x in my_combinations]
[66, 77, 88, 5082, 5808, 6776, 447216]

min(products_list)
66

获得子序列后，我们应用列表理解和 reduce() 来获取 my_combinations 列表中所有子序列的产品列表。然后我们应用 min() 函数从 products_list 中得到最小乘积，这将给出我们的答案。

Answer 5

接受的答案对所有正整数都是正确的，因为您不能将最小元素乘以任何数字并得到较小的结果。如果您获得的所有切片长度都大于 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.

Answer 6

def solution(a_list):

    sub = [[]]

    for i in range(len(a_list)):
        for j in range(len(a_list)):
            if(i == j):
                sub.append([a_list[i]])
            elif(i > j):
                sub.append([a_list[j],a_list[i]])
    sub.append(a_list)
    return sub


solution([10, 20, 30])

[[], [10], [10, 20], [20], [10, 30], [20, 30], [30], [10, 20, 30]]

在给定范围内查找列表的所有可能子列表的高效和 Pythonic 方法，以及将其中的所有元素相乘后的最小乘积？

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

python

reduce

list

python-2.7

python-3.x