Каков наилучший способ сравнить значения списка со списком списка?

Question

Проблема выглядит так: предположим, у нас есть 3 магазина и перечислены разные номера товаров. Каждый владелец магазина имеет следующие предметы:

Shop 1 : [2, 3]
Shop 2 : [1, 2]
Shop 3 : [4]
A=no of shops
dict = {shop_no:[item_list]}
need = set(items that are needed)

И мне нужен предмет [1,4], чтобы я мог его достичь, посетив магазин 2 и магазин 3.

Так что мой вопрос: как чтобы получить минимум магазинов, которые нужно посетить.

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

x=2**(A)
for i in range(1,x):
    count=0
    temp=[]
    for j in range(32):
        if i&(1<<j)>0:
            count+=1
            temp+=dict[j+1]
        temp=set(temp)
#Am generating items by combining shops and then doing a set difference
        if len(need-temp)==0: 
            return count
     return -1

Кто-то предложил мне алгоритм Рабина Карпа, Как я могу это реализовать ???

Answer 1

Вот мое глупое решение с использованием грубой силы:

from itertools import combinations
from typing import Dict, Set


shops = {
    1: {2, 3},
    2: {1, 2},
    3: {4},
}
need = {1, 4}


def shortest_visit(shops: Dict[int, Set[int]], need: Set[int]) -> Set[int]:
    for n in range(len(shops)):
        for visit in combinations(shops.keys(), n):
            if need <= {item for shop in visit for item in shops[shop]}:
                return set(visit)
    assert False, "Some of the needed items aren't available in any shop!"


print(shortest_visit(shops, need))

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

Answer 2

Вы можете использовать рекурсивный генератор вместе с functools.lru_cache, чтобы вычислить минимальное количество магазинов, необходимое для покупки определенного набора предметов:

from functools import lru_cache

@lru_cache()
def find_best_path(need: frozenset):
    return min(visit_shops(need), key=len)

def visit_shops(need):
    for k, items in shops.items():
        buy = items & need
        if buy == need:
            yield (k,)  # there's a single best option: just visit that shop
            break
        elif buy:
            yield (k,) + find_best_path(need - buy)

Тестирование на вашем пример:

shops = {
   'A': {2, 3},
   'B': {1, 2},
   'C': {4},
}
need = frozenset({1, 4})
print(find_best_path(need))  # ('B', 'C')

Тестирование на другом примере с несколькими параметрами:

shops = {
    'A': {1, 2, 3},
    'B': {4},
    'C': {5},
    'D': {1, 3, 5},
    'E': {2, 4},
}
need = frozenset({1, 2, 3, 4, 5})
print(find_best_path(need))  # ('D', 'E')