Python检查一个列表是否是另一个列表的子集，如果不是，如何拆分它？

Question

我该如何找到我的列表的最小数量，例如， 对于下面的列表，我可以很容易地发现莎拉的动物都属于家养动物使用set(sarahs_animals) < set(house_animals)

然而，约翰的动物需要分成动物园动物和家养动物。约翰动物可以通过多种方式分割，例如，也可以是家养动物、大型动物和鸟类动物，我如何找到可以分割的最小数量的列表？谢谢

johns_animals = ['dog', 'cat', 'rhino', 'flamingo']
sarahs_animals = ['dog', 'cat']

house_animals = ['dog', 'cat', 'mouse']
big_animals = ['elephant', 'horse', 'rhino']
bird_animals = ['robin', 'flamingo', 'budgie']
zoo_animals = ['rhino', 'flamingo', 'elephant']

Answer 1

我相信这是一个解决方案（Python3，但很容易适应Python2）。你知道吗

from itertools import combinations

johns_animals = {'dog', 'cat', 'rhino', 'flamingo'}

animal_sets = { 'house_animals': {'dog', 'cat', 'mouse'},
                'big_animals': {'elephant', 'horse', 'rhino'},
                'bird_animals': {'robin', 'flamingo', 'budgie'},
                'zoo_animals': {'rhino', 'flamingo', 'elephant'}
}

def minimal_superset(my_set):
  for n in range(1,len(animal_sets)+1):
    for set_of_sets in combinations(animal_sets.keys(), n):
      superset_union = set.union(*(animal_sets[i] for i in set_of_sets))
      if my_set <= superset_union:
        return set_of_sets

print(minimal_superset(johns_animals))

我们遍历所有可能的动物集合组合，返回第一个“掩盖”给定集合的组合my_set。因为我们从最小的组合开始，即由一个集合组成，然后前进到两个集合、三个集合等，所以找到的第一个集合保证是最小的（如果有几个相同大小的可能组合，则只找到其中一个）。你知道吗