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

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.