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

Question

It works fine, but it is slow.

Could anybody help make this faster?

import itertools
from decorators import timer
from settings import MENU, CASH
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):
 def __init__(self, cash, menu=MENU):
 self.__cash = cash
 self.__cheapest_cocktail = 10000
 self.__menu = self.__read_menu(menu)
 self.__matrix = self.__create_matrix()
 self.correct = []
 def __read_menu(self, menu):
 result = []
 for group in menu:
 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
 for cocktail in self.__menu:
 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

• SylvainD: Hello, could you please add some more information about what you are trying to achieve here? Thanks
• lmasikl: I try find all row combinations which sum elements equal any given number.
• Aseem Bansal: 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?
• SylvainD: 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).
• dnozay: I believe you are trying to solve the knapsack problem, here is an example: rosettacode.org/wiki/Knapsack_Problem/Python

Answer 1

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.