比较列表值与列表列表的最佳方法是什么？

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

[有人向我建议了rabin karp算法，我该如何实现？？？

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))

它的优点是先检查最短的组合，而不是在所有情况下都要强行通过它们的[[all，因此，如果有一个简短的解决方案，您会很快找到它。

Answer 2

您可以将递归生成器与functools.lru_cache一起使用，以计算购买特定商品集所需的最小商店数量：

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')