Here is some Python code that should implement Greedy Set Cover in linear time:
(Warning, it empties the input sets during the processing!)
from collections import defaultdict
F = [set([1,2,3]),
# First prepare a list of all sets where each element appears
D = defaultdict(list)
for y,S in enumerate(F):
for a in S:
# Now place sets into an array that tells us which sets have each size
for x,S in enumerate(F):
E= # Keep track of selected sets
# Now loop over each set size
for sz in range(max(len(S) for S in F),0,-1):
if sz in L:
P = L[sz] # set of all sets with size = sz
x = P.pop()
for a in F[x]:
for y in D[a]:
S2 = F[y]
It uses a dictionary D to store a list of all sets with a particular element.
It uses an array E to store which sets currently have each size. In other words, E[sz] will contain information about all the sets that currently have exactly sz elements.
The key to showing that this is linear is to observe that the innermost loop removes an element from a set, so cannot be executed more times than the total number of elements in all sets.