2

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

Curious_Student
  • 51
  • 1
  • 4
  • it's unclear what exactly you ask for. "solve for all points that equal a constant C and every direction is nonnegative".....solve what? if it's an equation, then what's the equation? It looks like some kind of Diofantine problem...which in general are unsolvable – Kermit the Frog Nov 11 '21 at 21:30
  • @KermittheFrog I reworded it, let me know if its still unclear – Curious_Student Nov 11 '21 at 21:36
  • Can you give an example? Depending on what you mean by 'duplicates', this appears to ask about finding [weak compositions of `C` of length n](https://en.wikipedia.org/wiki/Composition_(combinatorics)), or if order doesn't matter, asking for all [partitions](https://en.wikipedia.org/wiki/Partition_(number_theory)) of `C` with length <= n. – kcsquared Nov 11 '21 at 21:41
  • this is known as the knapsack problem, which is NP-hard. As far as I can see. See https://stackoverflow.com/questions/65637773/combinations-that-add-up-to-a-number-julia-lang – Kermit the Frog Nov 11 '21 at 21:44
  • There are somewhere between `2*((C/n)^n` and `C^n` different solutions to this problem. It will take your program a while to find and list all of them. That's one reason that versions of this problem that either seek to find one solution (knapsack) or merely to count all solutions (binomial summation) are more popular. – RBarryYoung Nov 11 '21 at 21:51
  • @kcsquared. The order doesnt matter. Examples: The solution of N=1 is (C). The solutions of N=2 and C = 2 are (2,0), (1,1), (0,2). – Curious_Student Nov 11 '21 at 22:11
  • 1
    The name for these is (weak) compositions of an integer, [see this post for a C++ version of your question](https://stackoverflow.com/questions/17461761/partition-and-composition-combinatorics-implementation-in-c) or [this one for a language-agnostic version.](https://stackoverflow.com/questions/2593781/print-all-ways-to-sum-n-integers-so-that-they-total-a-given-sum) – kcsquared Nov 11 '21 at 22:18
  • Is `x2` in your question `x²` or `x₂` ? – Aivean Nov 12 '21 at 00:01
  • @Aivean its x_2. – Curious_Student Nov 12 '21 at 13:41
  • I think I found a generialized algorithm to solve it without having to do trial and error. Atleast on paper it seems to check out. I am writing it and julia and I will post it as an answer if it works – Curious_Student Nov 12 '21 at 13:42
  • It's simpler than the Knapsack problem, since all sums equal C. Starting with n=1, x1=C, with n=2, (C-1,1) ... (C/2,C/2), with 3 (C-2,1,1) ... (C-3,2,1) ... (C/3,C/3,C/3) etc. Target is to never having xn+1 > xn (and for 7, n=2, you'd have max (4,3) since 7 is not divisible by 2, for instance). No duplicate in this case. – Déjà vu Nov 12 '21 at 14:51
  • 1
    Check the @kcsquared links. If you need to generate all partitions, there is no better way than to do it in O( len(results) ) time, which exactly what the "brute force" with running sum does. – Aivean Nov 12 '21 at 18:03

1 Answers1

1

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
Curious_Student
  • 51
  • 1
  • 4
  • I was going to suggest `Combinatorics.partitions`, but then I see that you want to allow 0s in your partitions. You might want to check out https://stackoverflow.com/questions/37296557/re-partitions too, although at a glance it seems likely that your version will be the fastest option. – Sundar R Nov 13 '21 at 00:31
  • Yeah I need it to be as fast as possible as my code calls it millions of times. Thanks for the suggestion though. – Curious_Student Nov 13 '21 at 18:37