Say I have n let's say it has a value of 27 now I have another variable lets say x is equals to 6 and a final variable z equals 9. We are going to find n by decrementing numbers from z with the amount of numbers equal to x.

For example, the number 27 should have an answer of 8 6 5 4 3 1 = 27 but the problem is you do not where to start, or how much the decrement value should be and also numbers cannot be duplicated. So the only solution I have now is to bruteforce it which takes soooo long. This is my current solution for it :

(idk if this works, I haven't got a "found" print)

for x in range(9**6):
    for a in range(9):
        for b in range(9):
            for c in range(9):
                for d in range(9):
                    for e in range(9):
                        for f in range(9):
                            _arr = [a, b, c, d, e, f]
                            arr = []
                            
                            for g in _arr:
                                if g not in _arr:
                                    arr.append(g)
                            
                            result = ((a   1)    (b   1)   (c   1)   (d   1)   (e   1)   (f   1))
                            if len(arr) == 6 and result == 27 :
                                print(f"→ found! | answer : {result}")

What algorithms or theories should I use to solve this, or if its even possible? So far I've looked into GMP, Numpy libraries etc. but do not know in what way I would implement those.

CodePudding user response：

There is no need to brute force this. You can start out by the minimum sum you can get with the number of terms (i.e., 1 2 3 4..). Then consider that the greatest value can be increased up to the maximum value. This increment can be applied to the second greatest as well, ...etc. We can determine by division how many of these increments we need. The remainder of this division will determine how much the greatest value that didn't change should be incremented.

Here is an implementation:

def solve(target, num_terms, max_value):
    total = num_terms * (num_terms   1) // 2  # Triangular number
    if total > target:
        raise ValueError("target is too small")
    need = target - total
    diff = max_value - num_terms
    if need > num_terms * diff:
        raise ValueError("target is too great")
    shift = need // diff
    if num_terms == shift:
        return list(range(max_value - shift   1, max_value   1))
    return (
        list(range(1, num_terms - shift))
          [num_terms - shift   (need % diff)]
          list(range(max_value - shift   1, max_value   1))
    )

Applied on the example in the question:

print(solve(27, 6, 9))  # [1, 2, 3, 4, 8, 9]

CodePudding user response：

Approach

• A backtracking approach worked quickly for the problem of number 27
• Backtracking was too slow for the larger number i.e. abandoned after 30 minutes on the more difficult problem of 780
• Was able to quickly solved both problems using Constraint Programming
• Implemented constraint programming using Google OrTools Constraint Satisfaction
• Stopped at first solution found with each run

Constraints

• Have a given number of numbers
• Numbers values range from 1 to a max value
• Numbers are distinct
• Numbers add to the desired sum

Performance

• OR-Tools was able to find solutions to the posted problems in milliseconds on a 10 -year-old Windows desktop

Code

from ortools.sat.python import cp_model

def find_factors(required_sum, max_value, n_numbers):
    '''
        Find factors that:
        : required_sum- sum to n
        : max_value numbers(numbers from 1 to max_value inclusive)
        - n_numbers - number of numbers to find
        
        Approach
        
        Use google ortools constraint satisfaction
        Reference: https://developers.google.com/optimization/cp
    '''

    # Create model
    model = cp_model.CpModel()

    # Create constraint variables
    number_choices = []
    for i in range(n_numbers):
        # numbers from 1 to max_value
        number_choices.append(model.NewIntVar(1, max_value, f"number {i}"))

    # Add constraints to variables
    #   Sum of numbers equals required sum
    model.Add(sum(number_choices)==required_sum)

    #   All numbers are different
    model.AddAllDifferent(number_choices)

    #   Numbers are in Descending order
    for i in range(n_numbers-1):
        model.Add(number_choices[i] > number_choices[i 1])

    # Solve for constsraints and report results
    solver = cp_model.CpSolver()
    status = solver.Solve(model)

    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        return ([solver.Value(v) for v in number_choices])
    else:
        return None  # no solution found

Testing

print(find_factors(27, 9, 6))
# Output: [9, 8, 4, 3, 2, 1]

print(find_factors(780, 102, 14))
# Output: [102, 59, 58, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46]

Timing

%timeit find_factors(27, 9, 6)
# Result: 3.13 ms ± 489 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit find_factors(780, 102, 14)
# Result: 7.95 ms ± 396 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)