Hello,
I am Maneesh i like to design a set which has all the possible ways of a combination of (3,5,10) of which when the sum is done we get a number.
example: 1
INPUT 13
If i give 13 as input, there are 2 set which can make 13 which are (3,10) and (5,5,3)
OUTPUT 2
example:2
INPUT 20
if i give 20 as input there are 4 ways to make 20 which are (3,3,3,3,3,5); (5,5,5,5); (10,10); (5,5,10).
OUTPUT 4
How can i write then programme?
Hey, why did you deleted it?
didnt think it was helpful enough
Nothing is bad or good, our perception makes it. And i might not value your code if i get it easily, rather if i will work hard to make it myself i will never forget and i will definitely value it alot.
This sounds like a kata. Well you could brute force this problem, building all combinations from the choices that total the sum. More likely, there is a solid mathematical approach to this that won’t take all that.
It’s too late in the evening for me to make a good approach, so here’s this instead:
from random import choice
import time
def MC_combinations(numb, choices, tolerance=5, timeout=0.5):
""" A very silly and impractical function to find "all" the ways selections from
a numerical list (choices) can be summed together to reach numb """
if numb < 1 or len([x for x in choices if x < 1]):
return 'Positive Values for numb and choices only'
result = []
tries_limit = tolerance * 200
stop_time = time.perf_counter() + timeout
while time.perf_counter() < stop_time:
r = []
tries = 0
catch = 0
brk = False
while sum(r) != numb:
if tries > tries_limit:
brk = not brk
break
elif catch == len(choices) + tolerance:
r = r[:-2]
catch = 0
elif sum(r) < numb: r.append(choice(choices))
elif sum(r) > numb:
r.pop()
tries += 1
catch += 1
if not brk:
r.sort()
if r not in result: result.append(r)
result.sort()
print(f'{len(result)} ways {choices} can be used to total {numb}')
return result
>>> print(MC_combinations(20, [3,5,10]))
4 ways [3, 5, 10] can be used to total 20
[[3, 3, 3, 3, 3, 5], [5, 5, 5, 5], [5, 5, 10], [10, 10]]
This came about mostly because your question got me debating the computational cost of brute-forcing it vs. building lists at random.
Thank you, so much. After i understand the algorithm i can write it in python. Thank you, for the code
Start with an empty list result to put all our combinations in.
r) to build a combination of elements from choices.sum(r), equals numb (the number each combination must sum up to)
sum(r) equals numb, add r to result if it isn’t already included. Then start again at step 1.sum(r) does not equal numb:
sum(r) is less than numb: randomly select an item from choices and add it to r & start step 2 again.sum(r) is greater than numb: Remove the last element from r & start step 2 again. If this happens repeatedly, give up on the current combination and start over at step 1.Do this repeatedly for a certain amount of time and return the resulting list of combinations. There’s no real guarantee you’ve found all possibilities but you can try giving the algorithm more time to search or raising/lowering the ‘give up on this combination’ threshold by changing the timeout and tolerance arguments.
There’s an attempt to crawl backward through r a small ways if it keeps getting stuck before giving up on that combination; honestly this part probably isn’t super necessary. Basically it makes an attempt to swap a few elements out on a failing list to get it to sum up to numb before starting a new combination. You could just add random elements to r until sum(r) is equal to numb, if it breaches numb, start over. This would make for an easier algorithm, but tested less reliable as it throws out a lot of combinations that ‘could have been’ given a few small changes only to have to remake them later.
If you’re going to attempt recreation, I should note it was made in Python v3.6
EDIT: I do feel obligated to tell you, just in case, this isn’t what you’d call a production-grade solution. If you set the timeout low and feed it a larger numb and/or a larger choices list and run it a few times you’ll probably notice the result isn’t always the same. Sometimes it’s found more or fewer possible solutions. That’s because this algo is a lot like giving monkeys typewriters and letting them hammer away at Shakespeare, given enough time…they’ll get lucky.
Thank you for the algorithm as well, kylec. I am actually a student, pursuing graduate, thanks for helping me out.
I was thinking to solve this question using permutation and combination method but failed to do so.
Oh, well in that case, this would be a rudimentary application of the Monte Carlo method. Randomly sample data (a set of possible numbers to pick) and model outcomes (sets of picks) that meet certain criteria (sets must sum to a specific number).
If you’re interested in solving problems in similar ways, check out PyMC3. It’s a great Python library for probabilistic programming and would make this solution considerably more elegant.
Another approach that’s overkill for small sums/sets but might handle larger values better could be evolutionary algorithms, specifically a genetic algorithm. Generate random seed lists of variable length then evolve them using the max sum threshold as a selective pressure. Introduce random mutations and deletions to the sets, mate them and have crossover events. Weed out the ones that breach our max sum and continue until we stop generating sets that total our desired sum. The library DEAP is great for this sort of thing, although it could be written by hand too.