如何找到一个列表和嵌套列表的交集？

Question

我有一个水果的列表：

fruits = ["apple","banana"]

我还有一个嵌套的篮子列表，每个篮子都是一个包含篮子名称（字符串）和水果列表的子列表。

baskets = [["basket1",["apple","banana","pear","strawberry"]],["basket2",["strawberry","pear","peach"]],["basket3",["peach","apple","banana"]]]

我想知道哪些篮子里包含了所有的水果，期望的结果是一个包含两个元素的列表，"basket1" 和 "basket3"。

我觉得用交集的方法最简单，所以我尝试了以下的做法：

myset = set(fruits).intersection(*map(set, set(baskets)))

但是我遇到了一个类型错误，提示“不可哈希的类型：'list'”。我明白列表不能直接用作映射，但我以为用“set”函数处理这两个列表可以把它们转换成集合……有没有其他方法可以找到一个列表和一个列表的交集呢？

Answer 1

你可以用你自己的方法这样做：

fruits = ["apple","banana"]
baskets = [["basket1",["apple","banana","pear","strawberry"]],
           ["basket2",["strawberry","pear","peach"]],
           ["basket3",["peach","apple","banana"]]]

fruitset = set(fruits)
res =  set(b for b, s in ((b, set(c)) for b, c in baskets) if s & fruitset)
print res  # --> set(['basket1', 'basket3'])

Answer 2

你不能对集合进行哈希，就像你不能对列表进行哈希一样。它们都有一个共同的问题：因为它们是可变的，里面的值可以改变，这样一来，任何包含它的集合或字典就会突然变得无效。

不过，你可以对它们的不可变版本进行哈希，比如 tuple 和 frozenset。

---

而且，讽刺的是，你现在面临的问题正是因为你试图解决这个问题。我们来拆解一下这一行：

myset = set(fruits).intersection(*map(set, set(baskets)))

第一部分是：

baskets_set = set(baskets)

你有一个列表的列表。你在用 set(baskets) 尝试创建一个列表的集合。但这是不行的，因为列表是不能哈希的。

---

如果你去掉这一部分，改用 map(set, baskets)，那么你就会得到一个集合的迭代器，这样是完全有效的。

当然，一旦你尝试去迭代它，它会试图从 baskets 的第一个元素（一个列表）创建一个集合，所以你又会遇到同样的错误。

---

而且，即使你解决了这个问题，逻辑上还是不太合理。比如说，三个字符串的集合和三个（不可变）字符串集合的交集是什么？是空的。因为这两个集合没有任何共同的元素。即使第二个集合中的某些元素包含了第一个集合的元素，也并不意味着第二个集合本身包含了第一个集合的任何元素。

Answer 3

你可以遍历每个篮子，检查一下这个fruits集合是否是当前篮子里水果的一个子集。如果是的话，就把当前篮子的名字存起来。

>>> fruits = {"apple", "banana"} #notice the {}, or `set(["apple","banana"])` in Python 2.6 or earlier
>>> [b for b, f in baskets if fruits.issubset(f)]
['basket1', 'basket3']