# Find all row combinations which sum elements equal to any given number

It works fine, but it is slow.

Could anybody help make this faster?

import itertools

from decorators import timer

class Cocktail(object):
def __init__(self, group, name, sell, count=0):
self.group = group
self.name = name
self.sell = sell
self.count = count

class Check(object):
self.__cash = cash
self.__cheapest_cocktail = 10000
self.__matrix = self.__create_matrix()
self.correct = []

result = []
key = group.keys()[0]
for cocktail in group[key]:
if self.__cheapest_cocktail > cocktail['sell']:
self.__cheapest_cocktail = cocktail['sell']

result.append(Cocktail(
key,
cocktail['name'],
cocktail['sell'],
))

return result

def __create_matrix(self):
result = []
max_count = self.__cash // self.__cheapest_cocktail
row = []
for i in range(0, max_count):
row.append(Cocktail(
cocktail.group,
cocktail.name,
cocktail.sell,
i
))

result.append(row)
return result

def find_combinations(self):
for check in itertools.product(*self.__matrix):
if sum([(c.sell * c.count) for c in check]) == self.__cash:
self.correct.append(check)

check = Check(CASH)
check.find_combinations()
check.__matrix size 80x25

• I try find all row combinations which sum elements equal any given number. – lmasikl Jul 14 '13 at 21:01
• What is check.__matrix size 80x25 after your code? Is it part of the code? Can you give a sample Input and output of your program so it can be easier to understand? – Aseem Bansal Jul 15 '13 at 6:28
• Probably not worth an answer but I think you should have a look at youtube.com/watch?v=o9pEzgHorH0 (I have no idea how many times I've posted a link to this video on this SE). – Josay Jul 15 '13 at 6:56
• I believe you are trying to solve the knapsack problem, here is an example: rosettacode.org/wiki/Knapsack_Problem/Python – dnozay Jul 15 '13 at 7:02

Take a look at Python Performace Tips and search for list comprehension. As far as I can understand your code you can use it.

An example would be this function.

def __create_matrix(self):
max_count = self.__cash // self.__cheapest_cocktail
return [ [Cocktail(cocktail.group,cocktail.name,cocktail.sell,i)
for i in xrange(0, max_count)] for cocktail in self._menu]


You don't need to create a list if you are not using it elsewhere. In the find_combinations function you can avoid the overhead of list creation because you are only interested in the sum of the elements.

def find_combinations(self):
for check in itertools.product(*self.__matrix):
if sum((c.sell * c.count) for c in check) == self.__cash:
self.correct.append(check)


I think there is a bug in your code. You are using a classCocktail but using cocktail in your code. I understand they are different but I think you have messed up C with c in your code in the __read_menu function. It is confusing whether or not you have messed it up.

That is all I can think of because I don't understand what the code is doing unless. Please edit your question to add sample input and output.