universe u of n elements collection of subsets of u s s1 s2 sm where every substet si has an associated cost find a minimum cost subcollection of s that covers all elements of u example u 1 2 3 4 5 s s1 s2 s3 s1 4 1 3 costs1 5 s2 2 5 costs2 10 s3 1 4 3 2 costs3 3 output set cover s2 s3 min cost 13 calculate the powerset of any iterable for a range of integers up to the length of the given list make all possible combinations and chain them together as one object from https docs python org3libraryitertools htmlitertoolsrecipes optimal algorithm dont use on big inputs o2n complexity finds the minimum cost subcollection os s that covers all elements of u args universe list universe of elements subsets dict subsets of u s1 elements s2 elements costs dict costs of each subset in s s1 cost s2 cost approximate greedy algorithm for setcovering can be used on large inputs though not an optimal solution args universe list universe of elements subsets dict subsets of u s1 elements s2 elements costs dict costs of each subset in s s1 cost s2 cost elements don t cover universe invalid input for set cover track elements of universe covered find set with minimum cost elementsadded ratio set may have same elements as already covered newelements 0 check to avoid division by 0 error union universe u of n elements collection of subsets of u s s1 s2 sm where every substet si has an associated cost find a minimum cost subcollection of s that covers all elements of u example u 1 2 3 4 5 s s1 s2 s3 s1 4 1 3 cost s1 5 s2 2 5 cost s2 10 s3 1 4 3 2 cost s3 3 output set cover s2 s3 min cost 13 calculate the powerset of any iterable for a range of integers up to the length of the given list make all possible combinations and chain them together as one object from https docs python org 3 library itertools html itertools recipes optimal algorithm dont use on big inputs o 2 n complexity finds the minimum cost subcollection os s that covers all elements of u args universe list universe of elements subsets dict subsets of u s1 elements s2 elements costs dict costs of each subset in s s1 cost s2 cost approximate greedy algorithm for set covering can be used on large inputs though not an optimal solution args universe list universe of elements subsets dict subsets of u s1 elements s2 elements costs dict costs of each subset in s s1 cost s2 cost elements don t cover universe invalid input for set cover track elements of universe covered find set with minimum cost elements_added ratio set may have same elements as already covered new_elements 0 check to avoid division by 0 error union
from itertools import chain, combinations




def powerset(iterable):
    
    "list(powerset([1,2,3])) --> [(), (1,), (2,), (3,), (1,2), (1,3), (2,3), (1,2,3)]"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))


def optimal_set_cover(universe, subsets, costs):
    
    pset = powerset(subsets.keys())
    best_set = None
    best_cost = float("inf")
    for subset in pset:
        covered = set()
        cost = 0
        for s in subset:
            covered.update(subsets[s])
            cost += costs[s]
        if len(covered) == len(universe) and cost < best_cost:
            best_set = subset
            best_cost = cost
    return best_set


def greedy_set_cover(universe, subsets, costs):
    
    elements = set(e for s in subsets.keys() for e in subsets[s])
    
    if elements != universe:
        return None

    
    covered = set()
    cover_sets = []

    while covered != universe:
        min_cost_elem_ratio = float("inf")
        min_set = None
        
        for s, elements in subsets.items():
            new_elements = len(elements - covered)
            
            
            if new_elements != 0:
                cost_elem_ratio = costs[s] / new_elements
                if cost_elem_ratio < min_cost_elem_ratio:
                    min_cost_elem_ratio = cost_elem_ratio
                    min_set = s
        cover_sets.append(min_set)
        
        covered |= subsets[min_set]
    return cover_sets


if __name__ == '__main__':
    universe = {1, 2, 3, 4, 5}
    subsets = {'S1': {4, 1, 3}, 'S2': {2, 5}, 'S3': {1, 4, 3, 2}}
    costs = {'S1': 5, 'S2': 10, 'S3': 3}

    optimal_cover = optimal_set_cover(universe, subsets, costs)
    optimal_cost = sum(costs[s] for s in optimal_cover)

    greedy_cover = greedy_set_cover(universe, subsets, costs)
    greedy_cost = sum(costs[s] for s in greedy_cover)

    print('Optimal Set Cover:')
    print(optimal_cover)
    print('Cost = %s' % optimal_cost)

    print('Greedy Set Cover:')
    print(greedy_cover)
    print('Cost = %s' % greedy_cost)