Imprime toutes les manières d'additionner n entiers de sorte qu'ils totalisent une somme donnée.

Question

J'essaye de trouver un algorithme qui imprimera toutes les manières possibles de sommer N entiers de sorte qu'ils totalisent une valeur donnée.

Exemple. Imprimer toutes les façons de résumer 4 entiers pour que leur somme à être 5.

Résultat devrait être quelque chose comme:

5 0 0 0 
4 1 0 0 
3 2 0 0 
3 1 1 0 
2 3 0 0 
2 2 1 0 
2 1 2 0 
2 1 1 1 
1 4 0 0 
1 3 1 0 
1 2 2 0 
1 2 1 1 
1 1 3 0 
1 1 2 1 
1 1 1 2 

Answer 1

Ceci est basé sur le code d'Alinium.
Je l'ai modifié afin qu'il imprime toutes les combinaisons possibles, car il fait déjà toutes les permutations.
En outre, je ne pense pas que vous ayez besoin de la boucle for lorsque n = 1, car dans ce cas, un seul nombre doit faire en sorte que la somme soit égale à la valeur.
Diverses autres modifications pour que les cas limites fonctionnent.

def sum(n, value): 
    arr = [0]*n # create an array of size n, filled with zeroes 
    sumRecursive(n, value, 0, n, arr); 

def sumRecursive(n, value, sumSoFar, topLevel, arr): 
    if n == 1: 
     if sumSoFar <= value: 
      #Make sure it's in ascending order (or only level) 
      if topLevel == 1 or (value - sumSoFar >= arr[-2]): 
       arr[(-1)] = value - sumSoFar #put it in the n_th last index of arr 
       print arr 
    elif n > 0: 
     #Make sure it's in ascending order 
     start = 0 
     if (n != topLevel): 
      start = arr[(-1*n)-1] #the value before this element 

     for i in range(start, value+1): # i = start...value 
      arr[(-1*n)] = i # put i in the n_th last index of arr 
      sumRecursive(n-1, value, sumSoFar + i, topLevel, arr) 

sommes Montre Running (4, 5) retourne:
[0, 0, 0, 5]
[0, 0, 1, 4]
[0, 0, 2, 3]
[0, 1, 1, 3]
[1, 1, 1, 2]

Answer 2

Je n'ai pas testé:

 
    procedure allSum (int tot, int n, int desiredTotal) return int 
     if n > 0 
      int i = 
      for (int i = tot; i>=0; i--) { 
       push i onto stack; 
       allSum(tot-i, n-1, desiredTotal); 
       pop top of stack 
      } 
     else if n==0 
      if stack sums to desiredTotal then print the stack end if 
     end if 

Je suis Bien sûr, il y a une meilleure façon de le faire.

Answer 3

La clé pour résoudre le problème est la récursivité. Voici une implémentation de travail en python. Il imprime toutes les permutations possibles qui se résument au total. Vous voudrez probablement vous débarrasser des combinaisons en double, éventuellement en utilisant un mécanisme de Set ou de hachage pour les filtrer.

def sum(n, value): 
    arr = [0]*n # create an array of size n, filled with zeroes 
    sumRecursive(n, value, 0, n, arr); 

def sumRecursive(n, value, sumSoFar, topLevel, arr): 
    if n == 1: 
     if sumSoFar > value: 
      return False 
     else: 
      for i in range(value+1): # i = 0...value 
       if (sumSoFar + i) == value: 
        arr[(-1*n)] = i # put i in the n_th last index of arr 
        print arr; 
        return True 

    else: 
     for i in range(value+1): # i = 0...value 
      arr[(-1*n)] = i # put i in the n_th last index of arr 
      if sumRecursive(n-1, value, sumSoFar + i, topLevel, arr): 
       if (n == topLevel): 
        print "\n" 

Avec un effort supplémentaire, cela peut probablement être simplifié pour se débarrasser de certains des paramètres je passe à la fonction récursive. Comme suggéré par le pseudo-code de redcayuga, l'utilisation d'une pile, au lieu de gérer manuellement un tableau, serait également une meilleure idée.

Answer 4

En mathématiques pures, un moyen de sommation entiers pour obtenir un total donné est appelé une partition. Il y a beaucoup d'informations autour de si vous google pour "partition entière". Vous recherchez des partitions entières contenant un nombre spécifique d'éléments. Je suis sûr que vous pourriez prendre l'un des mécanismes générateurs connus et adapter pour cette condition supplémentaire. Wikipedia a un bon aperçu du sujet Partition_(number_theory). Mathematica a même une fonction pour faire ce que vous voulez: IntegerPartitions[5, 4].

Answer 5

j'ai trouver un moyen de Ruby avec la spécification de domaine basé sur le code de Alinium

class Domain_partition 

    attr_reader :results, 
       :domain, 
       :sum, 
       :size 

    def initialize(_dom, _size, _sum) 
     _dom.is_a?(Array) ? @domain=_dom.sort : @domain= _dom.to_a 
     @results, @sum, @size = [], _sum, _size 
     arr = [0]*size # create an array of size n, filled with zeroes 
     sumRecursive(size, 0, arr) 
    end 

    def sumRecursive(n, sumSoFar, arr) 

     if n == 1 
      #Make sure it's in ascending order (or only level) 
      if sum - sumSoFar >= arr[-2] and @domain.include?(sum - sumSoFar) 
       final_arr=Array.new(arr) 
       final_arr[(-1)] = sum - sumSoFar #put it in the n_th last index of arr 
       @results<<final_arr 
      end 

     elsif n > 1 

      #********* dom_selector ******** 

      n != size ? start = arr[(-1*n)-1] : start = domain[0] 
      dom_bounds=(start*(n-1)..domain.last*(n-1)) 

      restricted_dom=domain.select do |x| 

       if x < start 
        false; next 
       end 

       if size-n > 0 
        if dom_bounds.cover? sum-(arr.first(size-n).inject(:+)+x) then true 
        else false end 
       else 
        dom_bounds.cover?(sum+x) ? true : false 
       end 
      end # *************************** 

      for i in restricted_dom 
       _arr=Array.new(arr) 
       _arr[(-1*n)] = i 
       sumRecursive(n-1, sumSoFar + i, _arr) 
      end 
     end 
    end 
end 

a=Domain_partition.new (-6..6),10,0 
p a 

b=Domain_partition.new [-4,-2,-1,1,2,3],10,0 
p b 

Answer 6

Si vous êtes intéressé à générer (lexicalement) commandé partitions entières, soit des ensembles non ordonnés uniques de S entiers positifs (pas des 0) cette somme à N, puis essayez ce qui suit. (désordonné signifie simplement que [1,2,1] et [1,1,2] sont la même partition)

Le problème n'a pas besoin de récursivité et est rapidement traité car le concept de recherche de la partition restreinte lexicale suivante est en fait très simple ...

En cours: À partir du dernier ajout (entier), recherchez la première instance où la différence entre deux addenda est supérieure à 1. Divisez la partition en deux à ce stade. Supprimer 1 de l'entier supérieur (qui sera le dernier entier dans une partie) et ajouter 1 à l'entier inférieur (le premier entier de la dernière partie). Recherchez ensuite la première partition lexicale ordonnée pour la dernière partie ayant le nouvel entier le plus grand comme valeur d'ajout maximale. J'utilise Sage pour trouver la première partition lexicale parce qu'elle s'éclaircit rapidement, mais c'est facile à faire sans elle. Enfin, rejoignez les deux parties et voilà! Vous avez la partition lexicale suivante de N ayant des parties S.

par exemple. [6,5,3,2,2] -> [6,5], [3,2,2] -> [6,4], [4,2,2] -> [6,4], [ 4,3,1] -> [6,4,4,3,1]

Donc, en Python et en appelant Sage pour la tâche mineure de trouver la première partition lexicale donnée parties n et s ...

from sage.all import * 

def most_even_partition(n,s): # The main function will need to recognize the most even partition possible (i.e. last lexical partition) so it can loop back to the first lexical partition if need be 
    most_even = [int(floor(float(n)/float(s)))]*s 
    _remainder = int(n%s) 

    j = 0 
    while _remainder > 0: 
     most_even[j] += 1 
     _remainder -= 1 
     j += 1 
    return most_even 

def portion(alist, indices): 
    return [alist[i:j] for i, j in zip([0]+indices, indices+[None])] 


def next_restricted_part(p,n,s): 
    if p == most_even_partition(n,s):return Partitions(n,length=s).first() 

    for i in enumerate(reversed(p)): 
     if i[1] - p[-1] > 1: 
      if i[0] == (s-1): 
       return Partitions(n,length=s,max_part=(i[1]-1)).first() 
      else: 
       parts = portion(p,[s-i[0]-1]) # split p (soup?) 
       h1 = parts[0] 
       h2 = parts[1] 
       next = list(Partitions(sum(h2),length=len(h2),max_part=(h2[0]-1)).first()) 
       return h1+next 

Si vous voulez des zéros (pas des partitions entières réelles), alors les fonctions n'ont besoin que de petites modifications.

Answer 7

Essayez ce code. J'espère que c'est plus facile à comprendre. Je l'ai testé, il génère une séquence correcte.

void partition(int n, int m = 0) 
{ 
    int i; 
    // if the partition is done 
    if(n == 0){ 
     // Output the result 
     for(i = 0; i < m; ++i) 
      printf("%d ", list[i]); 
     printf("\n"); 
     return; 
    } 
    // Do the split from large to small int 
    for(i = n; i > 0; --i){ 
     // if the number not partitioned or 
     // willbe partitioned no larger than 
     // previous partition number 
     if(m == 0 || i <= list[m - 1]){ 
      // store the partition int 
      list[m] = i; 
      // partition the rest 
      partition(n - i, m + 1); 
     } 
    } 
} 

Demander des éclaircissements, si nécessaire.

Le est une des sorties

6 
5 1 
4 2 
4 1 1 
3 3 
3 2 1 
3 1 1 1 
2 2 2 
2 2 1 1 
2 1 1 1 1 
1 1 1 1 1 1 


10 
9 1 
8 2 
8 1 1 
7 3 
7 2 1 
7 1 1 1 
6 4 
6 3 1 
6 2 2 
6 2 1 1 
6 1 1 1 1 
5 5 
5 4 1 
5 3 2 
5 3 1 1 
5 2 2 1 
5 2 1 1 1 
5 1 1 1 1 1 
4 4 2 
4 4 1 1 
4 3 3 
4 3 2 1 
4 3 1 1 1 
4 2 2 2 
4 2 2 1 1 
4 2 1 1 1 1 
4 1 1 1 1 1 1 
3 3 3 1 
3 3 2 2 
3 3 2 1 1 
3 3 1 1 1 1 
3 2 2 2 1 
3 2 2 1 1 1 
3 2 1 1 1 1 1 
3 1 1 1 1 1 1 1 
2 2 2 2 2 
2 2 2 2 1 1 
2 2 2 1 1 1 1 
2 2 1 1 1 1 1 1 
2 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1