Suppose I have a list of three products (A, B C). Each Product has a price. Given a total cost, I want to find all the possible product combinations to equal exactly that cost.
So far I've tried stuff like:
for price in product:
ret = []
for i in range(int(totalCost / price), -1, -1):
ret.append(i)
for c in range(1, len(products)+1, 1):
ret.append(int(products[c-1][1]/products[c][1]))
And here is where I get stuck. This will get me a list of possibilities, but it will only include the products that are later (than the current location) in the list. It won't wrap around to include the beginning, and thus, give me every possibility.
What do I need to do to get every possibility?
def possibilities(available_products, target_price):
if target_price == 0 or not available_products:
return []
this_price = available_products[0]
remaining_products = available_products[1:]
results = []
for qty in range(1 + target_price / this_price):
remaining_price = target_price - qty*this_price
if remaining_price == 0:
results.append([qty] + [0] * len(remaining_products))
else:
for option in possibilities(remaining_products, remaining_price):
results.append([qty] + option)
return results
That gives you:
pprint.pprint(possibilities([1, 2, 5], 10))
[[0, 0, 2],
[0, 5, 0],
[1, 2, 1],
[2, 4, 0],
[3, 1, 1],
[4, 3, 0],
[5, 0, 1],
[6, 2, 0],
[8, 1, 0],
[10, 0, 0]]
The itertools module offers combinatoric generators to help with problems such as this:
>>> from itertools import *
>>> prices = dict(a=10, b=15, c=8, d=2, e=5)
>>> total_cost = 20
>>> for r in range(1, 30):
for t in combinations_with_replacement(prices, r):
cost = sum(prices[p] for p in t)
if cost == total_cost:
print t
