Programme that works out all the different ways £2.50 can be made using any number of coins

Question

In england we have 1, 2, 5, 10, 20, 50 and a pound(100) p coins. Using these coins i would like to work out all the possible combinations that the coins can be added in to make £2.50. The way i approached this question was to make a list of all the possible combinations of all of the coins. To do this i did the following:

ps = [1, 2, 5, 10, 20, 50, 100]

list_of_combos = [[]]
for i in range(7):
    for j in range(7):
        for k in range(7):
            for l in range(7):
                for m in range(7):
                    for n in range(7):
                        for o in range(7):
                           print("processing..")
                           all_combos = (ps[i], ps[j], ps[k], ps[l], ps[m], ps[n], ps[o])
                           list_of_combos.append(all_combos)

Then from all the possible combos, i tried picking the only ones that actually add up to 250 by doing this.

for i in list_of_combos:
    if sum(i) == 250:
        print(i)

The problem i am having it that the first nested loop takes forever to complete, which basically makes the program useless. Is there anything i can do to make this loop finish quicker? Thanks.

Answer 1

I can give you an idea that might help. One idea to replace the loop, which I am not honestly sure how more/less efficient could be, but I expect to be better than the above is adapted from this:

How to get all possible combinations of a list’s elements?

Using the same function as the top answer:

list(itertools.combinations(iterable, r)) 

However, Keep in mind since you want to create a list of combinations of having more than one coin you might want to create a new list with repeated items.

HOWEVER this is a very very inefficient approach, One that will not get you a result due to the fact that you are limiting your combinations, as per this system you cannot ever have the answer be 250 1c coins for example

A better approach is to go the other way around, Starting from the biggest coins you can work from:

100 - 100 - 50

and go down, Dividing each coin in each different way, The advantage is that every operation you will do will be used to create a wanted result. So you are not wasting any loops (which in this approach is a lot) and you will not need to do any further checks to make sure its equal to the wanted results (e.g. 100 100 50 is a result, dividing you have for example 50 50 50 50 50 which is ALSO a result).

You might want to keep the checks to a limit of maybe 2-3 coin sizes down to improve performance and just loop each result and keep diving further to get every possible outcome