Search code examples
pythoncombinationspython-itertools

Can't understand why my implementation of Itertools.combinations_with_replacement is not working correctly


Cannot figure out why my code will not output the correct results of the itertools.combinations_with_replacement if for certain small values.

from itertools import combinations_with_replacement
menu = []
with open("menu.txt") as f:
    for line in f:
        budget = float(line.split("$")[-1])           # extract the budget
        break
    for line in f:                      
        itemName = line.split(",")[0]
        itemPrice = float(line.split("$")[-1])
        menu.append([itemName,itemPrice])
def shorten_list(menu):   # function to filter out items where price > budget
    i=0;                                
    for item in menu:
        if item[-1] > budget:
            del menu[i]
        i = i + 1
    return menu
shorten_list(menu)          #call to shorten_list function
for item in menu:
    item[-1] = int(item[-1]*100)    # cast to int to avoid floating point imprecision errors

budget = int(budget *100)     # cast to int to avoid floating point imprecision errors
flag = 0       # set a flag = 0 to check if solutions will be found
num_comb = 1
comb = [c for i in range(len(menu)+1) for c in combinations_with_replacement(menu, i)]      # outputs iterator with all possible combinations
print("\n")
for e in comb:
    if sum(l[1] for l in e) == budget:                  # filters out only the combinations that == our budget
        print ("Combination_with_R number " + str(num_comb)  + " is:") 
        print ([l[0] for l in e])                       # print only the item name
        print ("\n")
        num_comb += 1 
        flag = 1                        # if an solutions found we set flag = 1
    if flag == 0:           # if no solutions found, flag = 0 has not changed 
    print ("There is no combination of dishes that will equal your budget... Leave the change as tip! \n\n ")

The problem that I am having with the code is mostly when I need a combination to repeat a certain menu item to create a meal. For example if we have the menu item bread,$1.00 and the budget = 18 there should be a combination ['bread', 'bread','bread','bread'..... n=18] so essentially 18 breads. Or if the item is ketchup_packet,$0.10 and budget = 18 there should also be a combination of ['ketchup_packet',............ n = 180]. Assume that menu.txt is in this format:

$18.00
mixed fruit,$2.15
french fries,$2.75
side salad,$3.35
hot wings,$3.55
mozzarella sticks,$4.20
sampler plate,$5.80
pasta3,$5.05
salad,$3.25
pasta10,$10.10
pasta1,$2.65
TESTER,$1.20

For some reason with this menu.txt it won't output a combination of ['TESTER', 'TESTER',..... N =15]

But if the menu.txt is:

$12.00
mixed fruit,$2.15
french fries,$2.75
side salad,$3.35
hot wings,$3.55
mozzarella sticks,$4.20
sampler plate,$5.80
pasta3,$5.05
salad,$3.25
pasta10,$10.10
pasta1,$2.65
TESTER,$1.20

It will correctly output all combinations including ['TESTER','TESTER',..... n = 12]

It should also work with

$12.00
mixed fruit,$2.15
    french fries,$2.75
    side salad,$3.35
    hot wings,$3.55
    mozzarella sticks,$4.20
    sampler plate,$5.80
    pasta3,$5.05
    salad,$3.25
    pasta10,$10.10
    pasta1,$2.65
    TESTER,$0.01

But does not! Cannot understand why.


Solution

  • I cleaned up the code formatting, factored out a bunch of utility functions, and converted it to a linear programming problem. See what you think:

    from decimal import Decimal
    
    def get_name(s):
        return s.split(',')[0]
    
    def get_price(s):
        return Decimal(s.split('$')[-1])
    
    def get_menu(fname):
        with open(fname) as inf:
            budget = get_price(inf.next())
            items = [(get_name(line), get_price(line)) for line in inf]
        return budget, items
    
    def integer_linear_solver(coefficients, total, index=None):
        """
        Given coefficients [c0, c1, ... cN] and total,
        generate all integer solutions to the equation
            s0*c0 + s1*c1 + ... + sN*cN == total
        and return as [s0, s1, ... sN]
        """
        if index is None:
            # Start at the end and work back
            # (this avoids having to repeatedly slice coefficients)
            index = len(coefficients) - 1
    
        c = coefficients[index]
        max_s = total // c
    
        if index:  # more coefficients available - recurse
            for s in range(max_s + 1):    # [0 .. max_s]
                for sol in integer_linear_solver(coefficients, total - s*c, index-1):
                    yield sol + [s]
        else: # last coefficient
            if not(total % c):
                # no remainder -> exact solution found
                yield [max_s]
    
    def print_sol(coeffs, labels):
        items = ('{0} {1}'.format(c, l) for c,l in zip(coeffs, labels) if c > 0)
        print(', '.join(items))
    
    def main():
        budget,items = get_menu('menu.txt')
        names,prices = zip(*items)
    
        solutions = 0
        for sol in integer_linear_solver(prices, budget):
            print_sol(sol, names)
            solutions += 1
    
        if solutions:
            print('{} solutions found'.format(solutions))
        else:
            print("There is no combination of dishes that will equal your budget.")
    
    if __name__=="__main__":
        main()
    

    Run against your first example menu, it gives

    2 side salad, 2 hot wings, 1 mozzarella sticks
    2 french fries, 2 side salad, 1 sampler plate
    1 mixed fruit, 3 side salad, 1 sampler plate
    ...
    1 mixed fruit, 1 pasta1, 11 TESTER
    15 TESTER
    109 solutions found