correct me for using generators or tell me other way

Question

I have A menu dict item as key and price as value. There may exist a combination of item that will be bit cheaper than single item. For exa:

menu = {
    ('burger',) : 5.00,
    ('pizza',) : 12.00,
    ('coke',) : 4.00,
    ('macpuff',) : 4.00,
    ('pasta',) : 3.00,
    ('french_fries',) : 2.00,
    ('burger', 'coke', 'french_fries') : 10.00,
    ('pizza', 'coke') : 15.00,
}

Now suppose i ordered few items then output will be min-amount of given order:

I/P >  burger, coke 
O/P >  9      (5.00 + 4.00) 

I/P >  burger, coke, french_fries
O/P >  10.00 

I/P >  pizza, coke, french_fries
O/P >  17.00    (15.00 + 2.00)

here is the code i tried so for all prices which i will use as generators:

def isSubset(a, b):
    """
        compare two iterable and return true if first is subset of second
    """
    b = list(b)
    if not hasattr(a, '__iter__'):
        a = [a]
    for each in a: 
        try:
            b.remove(each)
        except ValueError:
            return False
    return True

def rest_min_price(order):
    if order:
        for item, price in menu.iteritems():
            if isSubset(order[0], item):
                new_order = order[1:]
                for itm in item:
                    try:
                        new_order.remove(itm)
                    except ValueError:
                        pass
                yield price + rest_min_price(new_order)

but when i run this it's saying type error:

for each in rest_min_price(order_item):
    print each

TypeError: unsupported operand type(s) for +: 'int' and 'generator'

Answer 1

Thank you all for your response. somewhere i used your suggestion and now i had solved it by same approach with different implementation.

here is my code :

class Rest_Menu():
    def __init__(self, menu):
        self.menu = menu
        self.all_price = [] 

    def min_price(self, order, total_price=0):
        """
        Return minm menu price by calculating all possible combination.
        """
        if order:
            for item, price in self.menu.iteritems():
                if isSubset(order[0], item):
                    new_order = [each for each in order]
                    for itm in item:
                        try:
                            new_order.remove(itm)
                        except ValueError:
                            pass
                    self.min_price(new_order, price+total_price)
        else:
            self.all_price.append(total_price)
        return min(self.all_price)

Thanks again. :)

Answer 2

You misunderstood yield. A function that contains yield magically becomes a generator. If you just call it, you get a generator object that you cannot directly use; you need to call its next() method to yank values from it. Most often you put it into a for loop.

>>> def genDemo(n):
...   while n > 0:
...     yield n
...     n -= 1
... 
>>> 
>>> gd = genDemo(3)
>>> gd
<generator object genDemo at 0x7fce12152820>
>>> gd.next()
3
>>> gd.next()
2
>>> gd.next()
1
>>> gd.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>> for x in genDemo(3):
...   print x
... 
3
2
1
>>> _

Your code is just a normal recursive function; it could use return.

Generators are handy when you don't want to get the whole sequence in memory; it makes most sense with very long and infinite sequences. You could generate permutations until you find the one you need, or generate random numbers until you find the one you need, or read from a socket until you get a quit message, etc.

Regarding subsets: you can't check for subsets lazily unless your data is ordered the same way. With the data sets you have, you'd be better off using built-in set.

Answer 3

Your problem comes in your attempt to combine a generator with recursion:

yield price + rest_min_price(new_order)

here price is an int, but rest_min_price() is a generator (because you yield, rather than return, its result), hence you cannot add them together and get a TypeError.

You need to loop through the items in your generator:

for item in rest_min_price(order_item):
    # process the item
    # yield result with price