Каков эффективный способ подсчета количества уникальных мультипликативных и аддитивных пар в списке целых чисел в Python?

Этот вопрос имеет математическое решение в закрытой форме, но если вы предпочитаете реализовать его на языке программирования, вам просто нужно найти все уникальные пары чисел из вашего списка и подсчитать число, удовлетворяющее вашим требованиям. 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)]

Базовая алгебра ... решите одну переменную с точки зрения другой:

xy >= x + y
xy - y >= x
y(x-1) >= x

Теперь, если все ваши элементы являются положительными целыми числами, вы получите

if x == 1, no solution
if x == 2, y >= 2
else x > 2
y >= x/(x-1)

В этом последнем случае x / (x-1) представляет собой дробь от 1 до 2; снова,

y >= 2

Решает неравенство.

Это дает вам тривиально доступное решение за время О (1); если вам нужны сами пары, вы ограничены печатью, которая составляет время О (п ^ 2).

Если вам нужно более математическое решение, учтите, что xy > x+y не имеет решений для y=1. В противном случае вы можете алгебраически обработать это до x > y/(y-1). Теперь, если у нас есть два последовательных целых числа положительный и разделив большее на меньшее, мы либо получим ровно 2 (если y = 2), либо получим некоторую дробь от 1 до 2, исключая. Обратите внимание, что x должен быть больше, чем это отношение y / (y-1), но также должно быть меньше y. Если y = 2, то единственное возможное значение x в нашем списке положительных целых чисел должно быть 1, и в этом случае совпадений нет, потому что 1 не больше 2/1. Таким образом, все это упрощается до «Для каждого числа y в нашем списке посчитайте все значения x, которые находятся в диапазоне [2, y)». Если вы сделаете математику, это должно привести к сложению 1 + 2 + 3 + ... + k, что является просто k(k+1)/2. Опять же, мы предполагаем, что n и k - положительные целые числа; вы можете вывести немного более сложную формулу, если учесть случаи для n <= 0.

Но если предположить, что вы ДЕЙСТВИТЕЛЬНО хотите придерживаться подхода грубой силы, а не прибегать к математическим рассуждениям, чтобы найти другой подход: я опробовал несколько вариантов, и вот более быстрое решение, основанное на следующем.

• Вы сказали, что список уже отсортирован, поэтому я отказался от функции сортировки.
• Точно так же "else: continue" не требуется, поэтому для простоты я отказался от него.
• Вместо того, чтобы перебирать все значения x и y, а затем проверять, является ли x <y, вы можете просто заставить свой второй цикл проверять значения y в диапазоне от x + 1 до y. НО...
• Вы можете использовать itertools для генерации уникальных пар всех чисел в вашем списке A
• Если вы в конечном итоге действительно заботитесь только о длине списка pairs, а не о самих парах чисел, тогда вы можете просто подсчитывать пары по пути, а не сохранять их. В противном случае у вас может закончиться нехватка памяти при высоких значениях N.
• Я получаю немного более быстрые результаты с эквивалентным тестом x (y-1) -y> 0. В большей степени, чем с x (y-1)> y.

Итак, вот что у меня есть:

def example4(A):
    mpair_count = 0
    for pair in itertools.combinations(A, 2):
        if pair[0]*(pair[1]-1) - pair[1] > 0:
            mpair_count += 1
    return mpair_count

Вот все рассчитано:

from timeit import default_timer as timer
import itertools

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)

# Cutting down the range
def example2(A):
    N = len(A)
    mpairs = []
    x = 0
    while x < N:
        for y in range(x+1,N):
            if (A[x]*A[y])>=(A[x]+A[y]):
                mpairs.append([A[x], A[y]])
        x += 1
    return len(mpairs)

# Using itertools
def example3(A):
    mpair_count = 0
    for pair in itertools.combinations(A, 2):
        if pair[0]*pair[1] > sum(pair):
            mpair_count += 1
    return mpair_count

# Using itertools and the different comparison
def example4(A):
    mpair_count = 0
    for pair in itertools.combinations(A, 2):
        if pair[0]*(pair[1]-1) - pair[1] > 0:
            mpair_count += 1
    return mpair_count

# Same as #4, but slightly different
def example5(A):
    mpair_count = 0
    for pair in itertools.combinations(A, 2):
        if pair[0]*(pair[1]-1) > pair[1]:
            mpair_count += 1
    return mpair_count

A = range(1,5000)
start = timer()
print(minimum_working_example(A))
end = timer()
print(end - start)

start = timer()
print(example2(A))
end = timer()
print(end - start)


start = timer()
print(example3(A))
end = timer()
print(end - start)

start = timer()
print(example4(A))
end = timer()
print(end - start)

start = timer()
print(example5(A))
end = timer()
print(end - start)

Результат:

12487503
8.29403018155
12487503
7.81883932384
12487503
3.39669140954
12487503
2.79594281764
12487503
2.92911447083

Итак, используя тот факт, что x*y >= x+y, если оба (ошибка в моем исходном комментарии), x и y - это >=2 (подробности см. В ответе @ Prune), тогда вы также можете удалить 0 и 1 из своего списка, если они появятся, потому что они не будут составить любую подходящую пару.

Итак, теперь, предполагая все числа или >=2 и у вас есть k из них (например, замените k на k-1 в следующей операции, если у вас есть n=1), все возможные пары будут удовлетворять вашему условию. А количество пар среди элементов k - это хорошо известная формула k*(k-1)/2 (погуглите, если не знаете). Время для вычисления этого числа по существу одинаково (одно умножение, одно деление) независимо от того, какое у вас значение k (если только вы не начнете переходить к сумасшедшим большим числам), поэтому сложность равна O (1).

Это предполагает, что ваши целые числа положительны, в противном случае формула будет немного сложнее, но все же возможно в качестве решения в закрытой форме.