set cover problem in python
def set_cover(universe, subsets): """Find a family of subsets that covers the universal set""" elements = set(e for s in subsets for e in s) # Check the subsets cover the universe if elements != universe: return None covered = set() cover = [] # Greedily add the subsets with the most uncovered points while covered != elements: subset = max(subsets, key=lambda s: len(s - covered)) cover.append(subset) covered |= subset return cover def main(): universe = set(range(1, 11)) subsets = [set([1, 2, 3, 8, 9, 10]), set([1, 2, 3, 4, 5]), set([4, 5, 7]), set([5, 6, 7]), set([6, 7, 8, 9, 10])] cover = set_cover(universe, subsets) print(cover) if __name__ == '__main__': main()
