Algorithme de résolution des partitions d'un entier

Question

Problème : x1+x2....xn=C où x1,x2....xn >= 0 et est un nombre entier. Trouvez un algorithme qui trouve chaque point (x1,x2...xn) qui résout ce problème.

Pourquoi : J'essaie d'itérer les termes d'un polynôme multivariable. Les puissances de chaque terme peuvent être décrites par les points ci-dessus. (Vous effectuez cette opération pour C = 0 à C = degré du polynôme)

J'essaie de créer un algorithme efficace qui ne produise que les solutions uniques (non dupliquées) et je voulais savoir s'il existait un algorithme existant.

Answer 1

Après avoir réfléchi à ce problème (et beaucoup de papier), voici mon algorithme : Il trouve toutes les combinaisons de tableaux de longueur N dont la somme est égale à k et dont les éléments sont supérieurs ou égaux à 0.

Cette méthode ne nécessite pas d'essais et d'erreurs pour obtenir la solution, mais elle implique un grand nombre de boucles. Une plus grande optimisation peut être faite en créant une fonction génératrice lorsque k et n sont connus à l'avance.

Si quelqu'un a un meilleur algorithme ou trouve un problème avec celui-ci, merci de le poster ci-dessous, mais pour l'instant ceci résout mon problème.

Merci à @kcsquared et @Kermit the Frog pour m'avoir conduit dans la bonne 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