Implementation of various approximation algorithms for set cover problem.

set-cover.py

# There are many greedy algorithms that could be used to pick a collection of sets that is close to as small as possible. Here are some that you will consider in this problem.

def isCovered(cover, allElems):
    coverElems = set()
    for s in cover:
        coverElems.update(s)
    return len(coverElems) == len(allElems)

def getAllElems(sets):
    elems = set()
    for s in sets:
        elems.update(s)
    return elems

# Dumb: Select sets for the collection in the order in which they appear on the list. Stop when all elements are covered.

def dumb(sets):
    idx, allElems = 0,  getAllElems(sets)
    while not isCovered(sets[0:idx], allElems):
        idx += 1
    return sets[0:idx]


# Simple: Consider sets in the order in which they appear on the list. When it is considered, select a set if it has at least one element that is not already covered. Stop when all elements are covered.

def simple(sets):
    idx, cover, coverElems = 0, [], set()
    allElems = getAllElems(sets)
    while not isCovered(cover, allElems):
        if len(sets[idx].difference(coverElems)) > 0:
            cover.append(sets[idx])
            coverElems.update(sets[idx])
        idx += 1

    return cover

# Largest-First: Consider sets in order of their size. If there are ties, break the tie in favor of the one that appears first on the list. When it is considered, select a set if it has at least one element that is not already covered. Stop when all elements are covered.
def largestFirst(sets):
    return simple(sorted(sets, key=len, reverse=True))

# Most-Help: Consider sets in order of the number of elements they contain that are not already covered. If there are ties, break the tie in favor of the one that appears first on the list. Stop when all elements are covered.
def mostHelp(sets):
    cover, coveredElems = [], set()
    allElems = getAllElems(sets)
    while not isCovered(cover, allElems):
        bestSet = max(sets, key=lambda s: len(s.difference(coveredElems)))
        coveredElems.update(bestSet)
        cover.append(bestSet)

    return cover

# Optimal:

import itertools as I

def setCover(sets):
    coverSize, allElems, cover = 0, getAllElems(sets), None

    while cover is None:
        coverSize += 1
        for candidate in I.combinations(sets, coverSize):
            if isCovered(candidate, allElems):
                cover = candidate
                break

    return cover


# Here is a list of sets: AB, BC, CD, DE, EF, FG, GH, AH, ADG, ADF
allSets = [set('AB'), set('BC'), set('CD'), set('DE'), set('EF'), set('FG'), set('GH'), set('ADG'), set('AH'), set('ADF')]

# First, determine the optimum solution, that is, the fewest sets that can be selected for a collection that covers all eight elements A,B,...,H. Then, determine the sizes of the collections that will be constructed by each of the four algorithms mentioned above. Compute the ratio of the size returned by the algorithm to the optimum size, and identify one of these ratios in the list below, correct to two decimal places.

print "An optimal cover: "    , setCover(allSets)
print "Dumb cover: "          , dumb(allSets)
print "Simple cover: "        , simple(allSets)
print "Largest-first cover: " , largestFirst(allSets)
print "Most-help cover: "     , mostHelp(allSets)