# Munkres algorithm in Python: calculating maximum profit

I'm using Munkres library from https://github.com/bmc/munkres/ to calculate maximum profit (reversed problem).

def get_no_of_vowels(str):
return sum(str.lower().count(c) for c in "aeiuoy")

def get_no_of_consonants(str):
return sum(str.lower().count(c) for c in "bcdfghjklmnpqrstvwxz")

def count_letters(str):
return sum(c.isalpha() for c in str)

def compute_ss(name, item):
if not count_letters(item)%2:
ss = get_no_of_vowels(name)*1.5
else:
ss = get_no_of_consonants(name)
if gcd(count_letters(name), count_letters(item)) > 1:
ss*=1.5
return ss

if __name__ == "__main__":
with open(sys.argv[1]) as f:
for line in f:
names = line.strip().split(';')[0].split(',')
items = line.strip().split(';')[1].split(',')
dic = collections.defaultdict(list)
profit_matrix = []
for name in names:
row = []
for item in items:
row.append(compute_ss(name, item))
profit_matrix.append(row)
m = Munkres()
cost_matrix = make_cost_matrix(profit_matrix, lambda x: 1e10 - x)
indexes = m.compute(cost_matrix)
total = 0
for row, column in indexes:
value = profit_matrix[row][column]
# print '(%.2f, %.2f) -> %.2f' % (row, column, value)
total += value
print "%.2f"%total

• It seems to be missing the necessary import statements. – Gareth Rees Oct 24 '13 at 16:22

I just want to point out two sources of inefficiency:

1) The counting functions, e.g.:

def get_no_of_vowels(str):
return sum(str.lower().count(c) for c in "aeiuoy")


This will loop over str 6 times, which is 5 more times than is necessary. A more efficient approach is:

def get_no_of_vowels(str):
return sum(1 for s in str if s.lower() in "aeiouy" else 0)


We are creating a generator that will convert each character into a 1 or a 0, and then just sum them. That way, we just do one iteration. Also, "y" is not a vowel.

        names = line.strip().split(';')[0].split(',')
items = line.strip().split(';')[1].split(',')


You are splitting line twice. That's extra work. Prefer:

names, items = line.strip().split(';')
names = names.split(',')
items = items.split(',')


Hope that helps.

• Your version of get_no_of_vowels raises a SyntaxError for me. You need sum(1 if s.lower() in "aeiouy" else 0 for s in str). (But: Python uses Iverson's convention, so you can actually write sum(s.lower() in 'aeiouy' for s in str).) – Gareth Rees Oct 28 '13 at 19:35