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

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

它的优点是首先检查最短的组合，而不是在所有情况下强行通过所有，所以如果有一个短的解决方案，你会相对较快地找到它。

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