Greedy Set Cover Sample Implementation

greedy_set_cover.py

def greedy_set_cover(universe, subsets, costs):
    covered = set()
    selection = []
    cover_cost = 0
    while (len(covered) < universe):
        # Cost effectiveness
        ce = [ float('inf') if len(uncovered) == 0 else (costs[i] / len(uncovered))
                for i in range(len(subsets))
                for uncovered in [subsets[i].difference(covered)] ]
        index = min(range(len(subsets)), key = lambda i: ce[i])
        selection.append(index)
        covered = covered.union(subsets[index])
        cover_cost = cover_cost + costs[index]
    return [selection, cover_cost]

if __name__ == '__main__':
    answer = greedy_set_cover(5,
            [ set([4, 1, 3]), set([2, 5]), set([1, 4, 3, 2]) ],
            [5, 10, 3])
    print(answer)