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

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

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

What is the best way to compare values of list over a list of list?

python

hash

dictionary

list

bitmask