Problem: x1+x2....xn=C where x1,x2....xn >= 0 and is a integer. Find an algorithm that finds every point (x1,x2...xn) that solves this.
Why: I am trying to iterate a multivariable polynomial's terms. The powers of each term can be described by the points above. (You do this operation for C = 0 to C = degree of the polynomial)
I am stuck trying to make an efficient algorithm that produced only the unique solutions (non duplicates) and wanted to see if there is any existing algorithm
After some thought on this problem (and alot of paper), here is my algorithm: It finds every combination of array of length N that sum to k and the elements are greater then or equal to 0.
This does not do trial and error to get the solution however it does involve quite alot of loops. Greater optimization can be made by creating a generating function when k and n are known beforehand.
If anyone has a better algorithm or finds a problem with this one, please post below, but for now this solves my problem.
Thank you @kcsquared and @Kermit the Frog for leading me in the right direction
""" Function that iterates a n length vector such that the combination sum is always equal to k and all elements are the natural numbers
.Returns if it was stopped or not
Invokes lambda function on every iteration
iteration_lambda (index_vector::Vector{T}, total_iteration::T)::Bool
Return true when it should end
"""
function partition(k::T, n::T, iteration_lambda::Function; max_vector = nothing, sum_vector = nothing, index_vector = nothing)::Bool where T
if n > 0
max_vector = max_vector == nothing ? zeros(T, n) : max_vector
sum_vector = sum_vector == nothing ? zeros(T, n) : sum_vector
index_vector = index_vector == nothing ? zeros(T, n) : index_vector
current_index_index::T = 1
total_iteration::T = 1
max_vector[1] = k
index_vector[1] = max(0, -(k * (n - 1)))
@label reset
if index_vector[current_index_index] <= max_vector[current_index_index]
if current_index_index != n
current_index_index += 1
sum_vector[current_index_index] = sum_vector[current_index_index - 1] + index_vector[current_index_index - 1]
index_vector[current_index_index] = max(0, -(k * (n - current_index_index - 1) + sum_vector[current_index_index]))
max_vector[current_index_index] = k - sum_vector[current_index_index]
else
if iteration_lambda(index_vector, total_iteration)
return true
end
total_iteration += 1
index_vector[end] += 1
end
@goto reset
end
if current_index_index != 1
current_index_index -= 1
index_vector[current_index_index] += 1
@goto reset
end
end
return false
end