-2

Before I state my question I want it to be known that I searched previous stack overflow questions, such as this one Python permutation, but they did not resolve my specific question.

Let's say I have a dictionary of fruits and their cost, along with a budget.

items = {'Apple': 1, 'Pear': 3, 'Orange': 2, 'Banana' : 4, 'Grape' : 3, 'Melon': 5, 'Lemon': 1}
budget = 10

I want to create something that will give an output of all possible item combinations I can buy. However, the following rules must be in place:

  1. I can only buy 1 of each fruit
  2. I must buy 4 fruits, no more no less
  3. Order doesn't matter. (i.e. I don't outputs of both [Apple Pear Orange Banana] and [Pear Apple Banana Orange], as they would be the same thing)
  4. I have to stay within the budget. Leftover money is fine (if there would be a way to return how much leftover money there is, that would be super cool), but I can't exceed 10.

I have followed examples with basic permutation and figured that out, but I can't seem to figure out how to do it with key value pairs and a 'budget'. Any help is appreciated. Thanks!

bismo
  • 1,257
  • 1
  • 16
  • 36

2 Answers2

1
  1. Create a list of tuples for convenience, eg [ (Apple, 1), (Banana, 2) ]
  2. Create all 4-tuple combinations
  3. Leave only those whose sum is under budget.
items = {'Apple': 1, 'Pear': 3, 'Orange': 2, 'Banana' : 4, 'Grape' : 3, 'Melon': 5, 'Lemon': 1}
budget = 10

tuples = items.items()

combos = list(itertools.combinations(tuples, 4))

combos_under_budget = [ t for t in combos if sum(p[1] for p in t) <= budget ]

combos_under_budget
>>> [(('Apple', 1), ('Pear', 3), ('Orange', 2), ('Banana', 4)),
 (('Apple', 1), ('Pear', 3), ('Orange', 2), ('Grape', 3)),
 (('Apple', 1), ('Pear', 3), ('Orange', 2), ('Lemon', 1)),
 (('Apple', 1), ('Pear', 3), ('Banana', 4), ('Lemon', 1)),
 (('Apple', 1), ('Pear', 3), ('Grape', 3), ('Lemon', 1)),
 (('Apple', 1), ('Pear', 3), ('Melon', 5), ('Lemon', 1)),
 (('Apple', 1), ('Orange', 2), ('Banana', 4), ('Grape', 3)),
 (('Apple', 1), ('Orange', 2), ('Banana', 4), ('Lemon', 1)),
 (('Apple', 1), ('Orange', 2), ('Grape', 3), ('Lemon', 1)),
 (('Apple', 1), ('Orange', 2), ('Melon', 5), ('Lemon', 1)),
 (('Apple', 1), ('Banana', 4), ('Grape', 3), ('Lemon', 1)),
 (('Apple', 1), ('Grape', 3), ('Melon', 5), ('Lemon', 1)),
 (('Pear', 3), ('Orange', 2), ('Banana', 4), ('Lemon', 1)),
 (('Pear', 3), ('Orange', 2), ('Grape', 3), ('Lemon', 1)),
 (('Orange', 2), ('Banana', 4), ('Grape', 3), ('Lemon', 1))]
ilyankou
  • 1,309
  • 8
  • 13
  • 3
    Instead of `zip`ing keys and values you can just use `items.items()`. – 0x5453 May 22 '20 at 17:15
  • 1
    @0x5453 Thanks, I included this in the answer. – ilyankou May 22 '20 at 17:18
  • 1
    This worked wonderfully. Now, an additional question. Let's say the first two fruits I buy are 1.5x their original cost, and the last two fruits I buy are the listed price. What edits can I make to your code to do this? Feel free to increase the budget in this instance in order to return more combinations. – bismo May 22 '20 at 17:19
  • 1
    @bismo `def get_total_price(c): a, b, c, d = [ p[1] for p in c ] return 1.5*(a+b) + (c+d)` And then your list comprehension will look something like that: [ c for c in combos if get_total_price(c) <= budget ] – ilyankou May 22 '20 at 17:29
1

The first item of the returned list ("lb") has the leftover. IMO, procedural paradigm (in general) is easier to read and debug. (BTW, this is my first attempt to answer at SO)

items = {'Apple': 1, 'Pear': 3, 'Orange': 2, 'Banana' : 4, 'Grape' : 3, 'Melon': 5, 'Lemon': 1}
budget = 10

import itertools
lk = list(items.keys())  # List of Keys
ltf = list(itertools.combinations(lk, 4))  # List of Tuples of Fruits

# Procedural
lb = []  # List under Budget
for tf in ltf:
    s = 0
    for f in tf:
        s += items[f]
    print(s, tf)
    if s <= budget:
        lb.append((budget - s, tf))  # Leftover, Tuple of Fruit
        print('Under budget\n')

A more functional code (with leftover). (The one-liner answer of @ilyankou is more elegant):

ls_tf = [(sum([items[f] for f in tf]), tf) for tf in ltf]
lb = [(budget - s_tf[0], s_tf[1]) for s_tf in ls_tf if (s_tf[0] <= budget)]

Out (procedural and functional):

[(0, ('Apple', 'Pear', 'Orange', 'Banana')),
 (1, ('Apple', 'Pear', 'Orange', 'Grape')),
 (3, ('Apple', 'Pear', 'Orange', 'Lemon')),
 (1, ('Apple', 'Pear', 'Banana', 'Lemon')),
 (2, ('Apple', 'Pear', 'Grape', 'Lemon')),
 (0, ('Apple', 'Pear', 'Melon', 'Lemon')),
 (0, ('Apple', 'Orange', 'Banana', 'Grape')),
 (2, ('Apple', 'Orange', 'Banana', 'Lemon')),
 (3, ('Apple', 'Orange', 'Grape', 'Lemon')),
 (1, ('Apple', 'Orange', 'Melon', 'Lemon')),
 (1, ('Apple', 'Banana', 'Grape', 'Lemon')),
 (0, ('Apple', 'Grape', 'Melon', 'Lemon')),
 (0, ('Pear', 'Orange', 'Banana', 'Lemon')),
 (1, ('Pear', 'Orange', 'Grape', 'Lemon')),
 (0, ('Orange', 'Banana', 'Grape', 'Lemon'))]

Print of procedural

10 ('Apple', 'Pear', 'Orange', 'Banana')
Under budget

9 ('Apple', 'Pear', 'Orange', 'Grape')
Under budget

11 ('Apple', 'Pear', 'Orange', 'Melon')
7 ('Apple', 'Pear', 'Orange', 'Lemon')
Under budget

11 ('Apple', 'Pear', 'Banana', 'Grape')
13 ('Apple', 'Pear', 'Banana', 'Melon')
9 ('Apple', 'Pear', 'Banana', 'Lemon')
Under budget

12 ('Apple', 'Pear', 'Grape', 'Melon')
8 ('Apple', 'Pear', 'Grape', 'Lemon')
Under budget

10 ('Apple', 'Pear', 'Melon', 'Lemon')
Under budget

10 ('Apple', 'Orange', 'Banana', 'Grape')
Under budget

12 ('Apple', 'Orange', 'Banana', 'Melon')
8 ('Apple', 'Orange', 'Banana', 'Lemon')
Under budget

11 ('Apple', 'Orange', 'Grape', 'Melon')
7 ('Apple', 'Orange', 'Grape', 'Lemon')
Under budget

9 ('Apple', 'Orange', 'Melon', 'Lemon')
Under budget

13 ('Apple', 'Banana', 'Grape', 'Melon')
9 ('Apple', 'Banana', 'Grape', 'Lemon')
Under budget

11 ('Apple', 'Banana', 'Melon', 'Lemon')
10 ('Apple', 'Grape', 'Melon', 'Lemon')
Under budget

12 ('Pear', 'Orange', 'Banana', 'Grape')
14 ('Pear', 'Orange', 'Banana', 'Melon')
10 ('Pear', 'Orange', 'Banana', 'Lemon')
Under budget

13 ('Pear', 'Orange', 'Grape', 'Melon')
9 ('Pear', 'Orange', 'Grape', 'Lemon')
Under budget

11 ('Pear', 'Orange', 'Melon', 'Lemon')
15 ('Pear', 'Banana', 'Grape', 'Melon')
11 ('Pear', 'Banana', 'Grape', 'Lemon')
13 ('Pear', 'Banana', 'Melon', 'Lemon')
12 ('Pear', 'Grape', 'Melon', 'Lemon')
14 ('Orange', 'Banana', 'Grape', 'Melon')
10 ('Orange', 'Banana', 'Grape', 'Lemon')
Under budget

12 ('Orange', 'Banana', 'Melon', 'Lemon')
11 ('Orange', 'Grape', 'Melon', 'Lemon')
13 ('Banana', 'Grape', 'Melon', 'Lemon')
Omr
  • 39
  • 4