CODEWITHSUNDEEP
python
attemptingpython
attemptingpython

Reputation: 79

Python - checking if a list is a subset of another list, if not, how do i split it?

How do I find the minimal amount of lists that mylist is in, for example, For the lists below, I can easily find that Sarah's animals all belong in house_animals using set(sarahs_animals) < set(house_animals)

However Johns animals needs split across zoo_animals and house_animals. John_animals could be split a number of ways e.g. it could also be house_animals, big_animals and bird_animals, how would I find the minimal amount of lists that it can be split across? Thanks

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

Upvotes: 1

Views: 124

Answers (1)

Błotosmętek
Błotosmętek

Reputation: 12927

I believe this is a solution (Python3, but easily adaptable to 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))

We go through all possible combinations of animal sets, returning the first combination that "covers up" the given set my_set. Since we start from smallest combinations, ie. consisting of one set, and advance to two-set, three-set etc., the first one found is guaranteed to be the smallest (if there are several possible combinations of the same size, just one of them is found).

Upvotes: 1

Related Questions