I came up with the following implementation for the Greedy Set Cover after much discussion regarding my original question here. From the help I received, I encoded the problem into a "Greedy Set Cover" and after receiving some more help here, I came up with the following implementation. I am thankful to everyone for helping me out with this. The following implementation works fine but I want to make it scalable/faster.
By scalable/faster, I mean to say that:
- My dataset contains about 50K-100K sets in S
- The number of elements in U itself is very small in the order of 100-500
- The size of each set in S could be anywhere from 0 to 40
And here goes my attempt:
U = set([1,2,3,4])
R = U
S = [set([1,2]),
set([1]),
set([1,2,3]),
set([1]),
set([3,4]),
set([4]),
set([1,2]),
set([3,4]),
set([1,2,3,4])]
w = [1, 1, 2, 2, 2, 3, 3, 4, 4]
C = []
costs = []
def findMin(S, R):
minCost = 99999.0
minElement = -1
for i, s in enumerate(S):
try:
cost = w[i]/(len(s.intersection(R)))
if cost < minCost:
minCost = cost
minElement = i
except:
# Division by zero, ignore
pass
return S[minElement], w[minElement]
while len(R) != 0:
S_i, cost = findMin(S, R)
C.append(S_i)
R = R.difference(S_i)
costs.append(cost)
print "Cover: ", C
print "Total Cost: ", sum(costs), costs
I am not an expert in Python but any Python-specific optimizations to this code would be really nice.
See Question&Answers more detail:
os