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'

Hippie

Note that list.remove only removes the first match found, you can use a LC here: new_order = [x for x in order[1:] if x not in item] – Quiteri

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. :)

Hippie

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.

Goldarn

thanks for reply i will try it with return. for second compliment: actually there can be more than 1 same-item in combo items and same as order-item can have more than 1 count of same type...hence we_cant use set here....:) – Hippie

Your set items are not just foods, but pairs of (food, quantity). The best representation is probably a dict with names as keys and quantities as values. Even better is something like defaultdict(int) that automatically sets the count to 0 for any item requested. You can directly compare such dicts. – Goldarn

@roshan: ...or you could maybe consider a Counter. – Arin

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

Displume

while addressing the error, that won't solve the task OP is facing – Flypaper

@Flypaper If I am not wrong then OP might need a DP based solution here. – Quiteri