I am trying to find all tuples containing only positive integers (0 allowed) that add to 100. I have some constraints on the max values for each index. I have the list maxs that include these constraints
maxs = [3, 9, 14, 21, 21, 35, 31, 49, 42, 38]
So far I am simply running this 10 dimensional nested for loop
combinations = []
for s1 in range(maxs[0] 1):
for s2 in range(maxs[1] 1):
for s3 in range(maxs[2] 1):
for s4 in range(maxs[3] 1):
for s5 in range(maxs[4] 1):
for s6 in range(maxs[5] 1):
for s7 in range(maxs[6] 1):
for s8 in range(maxs[7] 1):
for s9 in range(maxs[8] 1):
for s10 in range(maxs[9] 1):
if s1 s2 s3 s4 s5 s6 s7 s8 s9 s10 == 100:
combinations.append([s1,s2,s3,s4,s5,s6,s7,s8,s9,s10]
I know there are stictly less than 10^11 combinations if that helps at all. Maybe this problem is too large
Thanks
CodePudding user response:
Recursive approach. Example uses only three first entries. Acceleration is possible with early bad branch cutting - for example, when cursum exceeds target
maxs = [3, 9, 14, 21, 21, 35, 31, 49, 42, 38]
def sum100(n, target, maxs, level, cursum, curlist):
if level == n:
if cursum == target:
print(curlist)
return
for i in range(maxs[level] 1):
sum100(n, target, maxs, level 1, cursum i, curlist [i])
sum100(3, 15, maxs, 0, 0, [])
[0, 1, 14]
[0, 2, 13]
...
[1, 3, 11]
[1, 4, 10]
[1, 5, 9]
...
[3, 1, 11]
[3, 2, 10]
[3, 3, 9]
CodePudding user response:
This one is not the best performant one, but it is the easiest.
from itertools import combinations
maxs = [3, 9, 14, 21, 21, 35, 31, 49, 42, 38]
combination = [
tuple(filter(lambda x: 0 <= x <= 100, item))
for r in range(1, len(maxs))
for item in combinations(maxs, r)
]
result = [item for item in combination if sum(item) == 100]
print(result)