避免 python 中的多个嵌套 for 循环

Question

当一个嵌套for循环的范围达到外部for循环的当前迭代时，如何避免多个嵌套for循环？例如，考虑以下代码：该程序 returns 来自列表 arr 的三元组，使得 arr[i] - arr[j] = arr[j] - arr[k] = d 和 i<j<k.

d =3
arr = [1, 2, 4, 5, 7, 8, 10]
list1 = []

for biggest in range(0, len(arr)):
    for bigger in range(0, biggest):
        for big in range(0, bigger):
            if abs(arr[big] - arr[bigger]) == d and abs(arr[bigger] - arr[biggest]) == d:
                list1.append([arr[big], arr[bigger], arr[biggest]])
print(list1))

除了使用多个嵌套循环还有其他替代方法吗？

Answer 1

您可以使用 the combinations function from itertools。您的代码将变为：

from itertools import combinations

d = 3
arr = [1, 2, 4, 5, 7, 8, 10]
list1 = []
for big, bigger, biggest in combinations(arr, 3):
    if abs(big - bigger) == d and abs(bigger - biggest) == d:
        list1.append([big, bigger, biggest])

print(list1)

它给出与您的代码相同的打印输出（在您删除最后一行多余的右括号之后）：

[[1, 4, 7], [2, 5, 8], [4, 7, 10]]

请注意，我将变量 big、bigger、biggest 的含义更改为数组值而不是它们的索引。使用值并避免使用索引更像 pythonic 并且更容易理解。

您也可以在列表推导中这样做，以获得稍微不同的外观，避免临时列表，并可能提高速度。

from itertools import combinations

d = 3
arr = [1, 2, 4, 5, 7, 8, 10]
print([[big, bigger, biggest]
        for big, bigger, biggest in combinations(arr, 3)
        if abs(big - bigger) == d and abs(bigger - biggest) == d
    ])

Answer 2

您可以将三个循环替换为：

from itertools import combinations

for big, bigger, biggest in combinations(range(0, len(arr)), 3):

您可以将所有代码替换为：

print([t for t in combinations(arr, 3)
       if t[2] - t[1] == t[1] - t[0] == d])

Answer 3

虽然以前的答案是 pythonic，如果您关心搜索算法的实现，您可以通过实现二进制搜索算法在 [=19= 中查找 k 来将算法的复杂性从 O(N^3) 降低到 O(N^2logN) ] 在 j+1 和 lst 的长度之间，满足 d - abs(lst[j] - lst[k]) == 0.

d = 3
lst = [1, 2, 4, 5, 7, 8, 10]


def bsearch(lst, left, right, j):
    while left < right:
        k = (left + right) // 2

        diff = d - abs(lst[j] - lst[k])

        if diff == 0:
            return k
        if diff > 0:
            left = k + 1
        else:
            right = k

    return None


l, result = len(lst), []
for i in range(l):
    for j in range(i + 1, l):
        diff = d - abs(lst[i] - lst[j])

        if diff != 0: continue
        k = bsearch(lst, j + 1, l, j)

        if not k: continue
        result.append((lst[i], lst[j], lst[k]))

print(result)

[(1, 4, 7), (2, 5, 8), (4, 7, 10)]

Answer 4

我猜找到了更好的方法！避免嵌套循环。

arr = [1,2,3,4,5,6,7,8,9]
d = 3
list1 = arr
list2 = []
for each in (0,len(list1)):
    if list1[each] + d in arr and list1[each] + 2*d in arr:
         list2.append([list1[each], list1[each]+d, list1[each]+2*d])
print(list2)

避免 python 中的多个嵌套 for 循环

Avoiding multiple nested for-loops in python

python

for-loop

nested-loops