CODEWITHSUNDEEP
pythonmath
Marc Kelly
Marc Kelly

Reputation: 35

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

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

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

These would match:

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).

Upvotes: 2

Views: 119

Answers (4)

Arne
Arne

Reputation: 10545

This is a constraint satisfaction problem. These can often be solved by a method called dynamic 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.

Upvotes: 3

Alex Reynolds
Alex Reynolds

Reputation: 96984

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

Upvotes: 2

Mr5he11
Mr5he11

Reputation: 353

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.

Upvotes: 0

Lucas Roberts
Lucas Roberts

Reputation: 1343

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.

Upvotes: 1

Related Questions