Поиск набора товаров, образованных двумя списками - PullRequest
Новая
       24

Поиск набора товаров, образованных двумя списками

2 голосов
/ 23 октября 2019

Учитывая два списка, скажем, A = [1, 3, 2, 7] и B = [2, 3, 6, 3]

Найти набор всех продуктов, которые могут быть сформированы путем умножения числав A с числом в B. (Под набором я подразумеваю, что я не хочу дубликаты). Я ищу самое быстрое время работы. Хеш-функции недопустимы .

Первым подходом будет грубая сила, где мы умножаем каждое число от A на каждое число в B, и если мы находим продукт, которого еще нет всписок, затем добавьте его в список. Поиск всех возможных продуктов будет стоить O(n^2), а чтобы проверить, присутствует ли продукт в списке, он будет стоить O(n^2). Таким образом, общая сумма составляет O(n^4).

Я ищу, чтобы оптимизировать это решение. Первое, что приходит мне в голову, - это удалить дубликаты в списке B. В моем примере у меня есть 3 в качестве дубликата. Мне не нужно снова вычислять произведение всех элементов из A с дубликатом 3. Но это по-прежнему не помогает сократить общее время выполнения.

Я предполагаю, что самое быстрое время выполнения может быть O(n^2), если все числа в A и B вместе взятые являются уникальными И простыми. Таким образом гарантируется, что дубликатов не будет, и мне не нужно проверять, присутствует ли мой продукт в списке. Поэтому я думаю, сможем ли мы предварительно обработать наш входной список так, чтобы он гарантировал уникальные значения продукта (один из способов предварительной обработки - удалить дубликаты в списке B, как я уже упоминал выше).

Возможно ли этов O(n^2) времени, и будет ли это иметь значение, если я забочусь только о количестве уникальных возможных продуктов вместо фактических продуктов? 

for i = 1 to A.length:
    for j = 1 to B.length:
        if (A[i] * B[j]) not already present in list: \\ takes O(n^2) time to verify this
            Add (A[i] * B[j]) to list
        end if
    end for
end for

print list

Ожидаемый результат для вышеуказанного ввода: 2, 3, 6,9, 18, 4, 12, 14, 21, 42

РЕДАКТИРОВАТЬ:

Я могу придумать решение O(n^2 log n):

1) Я создаю все возможные продуктызначения, не беспокоясь о дубликатах \ Это O(n^2)

2) Сортировать эти значения продукта \ это будет O(n^2 log n), потому что у нас есть n ^ 2 числа для сортировки

3) Удалить дубликатыв линейном времени, так как элементы теперь отсортированы

1 Ответ

0 голосов
/ 23 октября 2019

Используйте наборы для устранения дубликатов. 

    A=[3, 6, 6, 8]
    B=[7, 8, 56, 3, 2, 8]
    setA = set(A)
    setB = set(B)
    prod=set()  #empty set

    [prod.add(i*j) for i in setA for j in setB]
    print(prod)
    {64, 448, 6, 168, 9, 42, 12, 16, 48, 18, 336, 21, 24, 56}

Сложность - O (n ^ 2).

Другой способ заключается в следующем. O (n ^ 3) сложность 

 prod=[]
    A=[1,2,2,3]
    B=[5,6,6,7]

    for i in A:
              for j in B:
                  if prod==[]:
                      prod.append(i*j)
                      continue
                  for k in range(len(prod)):
                    if i*j < prod[k]:
                     prod.insert(k,i*j)
                     break
                    elif i*j == prod[k]:
                     break
                    if k==len(prod)-1:
                     prod.append(i*j)
    print(prod)

Еще один способ. Это может быть внутреннее использование хеш-функций. 

   from toolz import unique
    A=[1,2,2,3]
    B=[5,5,7,8]
    print(list(unique([i*j for i in A for j in B])))
...