python - 在Python中计算整数列表中唯一乘法和加法对的数量的有效方法是什么？

Question

给定一个排序数组 A = [n, n+1, n+2,... n+k] 元素，我试图计算乘法和加法对的唯一数量，使得条件 xy >= x+y 是使满意。其中 x 和 y 是列表的索引，并且 y > x。

这是我使用天真的蛮力方法的最小工作示例：

def minimum_working_example(A):
    A.sort()
    N = len(A)
    mpairs = []
    x = 0
    while x < N:
        for y in range(N):
            if x<y and (A[x]*A[y])>=(A[x]+A[y]):
                mpairs.append([A[x], A[y]])               
            else:
                continue    
        x+=1
    return len(mpairs)  

A = [1,2,3,4,5]
print(minimum_working_example(A))
#Output = 6, Unique pairs that satisfy xy >= x+y: (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)

然而，这种方法对于大型列表具有指数时间复杂度。

存在哪些排序或搜索算法可以让我实现更有效的解决方案？

标签： pythonpython-3.xalgorithm

Answer 1

这个问题有一个封闭形式的数学解决方案，但如果您更喜欢用编程语言来实现，您只需要从您的列表中找到所有唯一的数字对，并计算满足您要求的数字。itertools.combinations你的朋友在这里吗：

import itertools

A = [1,2,3,4,5]
pairs = []
for x, y in itertools.combinations(A, 2):
    if x*y >= x + y:
        pairs.append((x,y))

输出

[(2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]