What is the math program I'm trying to solve in python?

user_9189577 0
Viewed 98

I am trying to solve this math problem in python, and I'm not sure what it is called:

  • The answer X is always 100
  • Given a list of 5 integers, their sum would equal X
  • Each integer has to be between 1 and 25
  • The integers can appear one or more times in the list

I want to find all the possible unique lists of 5 integers that match.

These would match:

  • 20,20,20,20,20
  • 25,25,25,20,5
  • 10,25,19,21,25

along with many more.

I looked at itertools.permutations, but I don't think that handles duplicate integers in the list. I'm thinking there must be a standard math algorithm for this, but my search queries must be poor.

Only other thing to mention is if it matters that the list size could change from 10 integers to some other length (6, 24, etc).

math python
4 Answers

This is a constraint satisfaction problem. These can often be solved by a method called linear programming: You fix one part of the solution and then solve the remaining subproblem. In Python, we can implement this approach with a recursive function:

def csp_solutions(target_sum, n, i_min=1, i_max=25):
    domain = range(i_min, i_max + 1)
    if n == 1:
        if target_sum in domain:
            return [[target_sum]]
        else:
            return []
    solutions = []
    for i in domain:
        # Check if a solution is still possible when i is picked:
        if (n - 1) * i_min <= target_sum - i <= (n - 1) * i_max:
            # Construct solutions recursively:
            solutions.extend([[i] + sol 
                              for sol in csp_solutions(target_sum - i, n - 1)])
    return solutions


all_solutions = csp_solutions(100, 5)

This yields 23746 solutions, in agreement with the answer by Alex Reynolds.

user_130141720

Another approach with Numpy:

#!/usr/bin/env python

import numpy as np

start = 1
end = 25
entries = 5
total = 100

a = np.arange(start, end + 1)
c = np.array(np.meshgrid(a, a, a, a, a)).T.reshape(-1, entries)
assert(len(c) == pow(end, entries))
s = c.sum(axis=1)

#
# filter all combinations for those that meet sum criterion
#

valid_combinations = c[np.where(s == total)]
print(len(valid_combinations))   # 23746

#
# filter those combinations for unique permutations
#

unique_permutations = set(tuple(sorted(x)) for x in valid_combinations)
print(len(unique_permutations))  # 376
user_194100

You want combinations_with_replacement from itertools library. Here is what the code would look like:

from itertools import combinations_with_replacement
values = [i for i in range(1, 26)]
candidates = []
for tuple5 in combinations_with_replacement(values, 5):
    if sum(tuple5) == 100:
        candidates.append(tuple5)

For me on this problem I get 376 candidates. As mentioned in the comments above if these are counted once for each arrangement of the 5-pair, then you'd want to look at all, permutations of the 5 candidates-which may not be all distinct. For example (20,20,20,20,20) is the same regardless of how you arrange the indices. However, (21,20,20,20,19) is not-this one has some distinct arrangements.

user_31641000

I think that this could be what you are searching for: given a target number SUM, a left treshold L, a right treshold R and a size K, find all the possible lists of K elements between L and R which sum gives SUM. There isn't a specific name for this problem though, as much as I was able to find.

user_130970650
Related