Décomposition en somme de n entiers

Version imprimable

03/12/2006, 23h35
netsabes

Décomposition en somme de n entiers

Bonjour,

je cherche à décomposer le nombre 45 en somme de n entiers non nuls (rangés dans l'ordre croissant) de toutes les manières possibles. Le nombre n varie de 1 à 45.

Je sens un problème de récursivité là-dessous.

Je programme en Delphi, au cas où vous me fourniriez une réponse dans un langage.

En fait, la liste de toutes les possibilités m'irait très bien, même sans algorithme. Tout ce que je souhaite, c'est la placer dans un tableau constant pour la réutiliser.

Cordialement,

Netsabes.

Bonjour,

effectivement, tu as bien compris qu'il y a un souci de récursivité là dessous

Code:

1
2
3
4
5
6
7
8
9
10
11
12
 
procédure maSomme(entier x , entier somme , entier N)
début
     pour i=x à N faire
          debut
                 Ajouter x à la solution
                 somme += x
                 si somme = N alors Afficher la solution
                 si somme < N alors maSomme(x+1, somme, N)
                 Retirer x de la solution
          fin
fin

Je pense que ça devrait être quelques chose comme ça.

Bonjour,

En supposant que n peut être différent dans chaque solution et que chaque entier ne peut-être utilisé qu'une fois, on poourraita voir un code qui pourrait ressembler à ceci (je n'ai pas codé l'objet Tsolution et les procédures AddSolutionToSolutionList, IsSolutionInSolutionList) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
procedure ProcessSolution(solution:Tsolution,c:integer) ;
// n : nombre faisant partie de la solution à décomposer en 2
begin 
if n>1 then begin 
      tempsolution:=Tsolution.create  ;
      tempsolution.assign(solution);
      tempsolution.DeleteItem(c) ;
      // on envisage toutes les possibilités de 
      // remplacement de c par a+b (c=a+b)
      for i:=1 to c div 2 do if (i<>c-i) begin 
          newsolution:=Tsolution.create  ;
          newsolution.assign(tempsolution);
          newsolution.AddItem(i) ;
          newsolution.AddItem(c-i) ;
          if not IsSolutionInSolutionList(newsolution) 
             then begin 
                    // si la soluce n'a pas déjà été trouvée,
                    AddSolutionToSolutionList(solution) ;
                    // on essaie de trouver récursivement de nouvelles soluces 
                    ProcessSolution(newsolution,i) 
                    ProcessSolution(newsolution,c-i) 
                     end 
             else newsolution.free ;
      tempsolution.free ;
      end ;
 
procedure buildSolutions ;
begin 
solution:=Tsolution.create ;
solution.AddItem(45) ; 
AddSolutionToSolutionList(solution) ;
ProcessSolution(solution,45) ;
...
// Ala fin, on libèrera tous les objets solutions de la liste des solutions

04/12/2006, 22h49
netsabes

Nullissimo

Merci Graffito et Toto13,

:oops: nul comme tout, je n'arrive pas à mettre en oeuvre vos propositions.

Est-il possible de me placer en pièce jointe le résultat sous forme d'un (8O gros8O ) fichier texte contenant :
45
44 1
43 2
43 1 1
42 3
42 2 1
42 1 1 1
etc...

merci par avance.

Netsabes, reconnaissant.
04/12/2006, 23h03
Trap D

Tu peux peut-être t'inspirer de ce qui a été écrit ici
05/12/2006, 01h21
thewho

Bonjour,

Après une recherche rapide, ce n'est peut-être pas si trivial qu'on le pense, voir entre autres

http://www.mjc-andre.org/pages/amej/.../99_parti.html
05/12/2006, 08h48
ToTo13

Bonjour,

Etant donné que tu travaille en Delphi...
si tu traduis en anglais ma petite procédure, tu auras déjà le corp.
Il te reste ensuite à créer la liste résultat et là deux solutions :
- Tu connais les listes chainées... et tu en fais une.
- Tu ne le maitrises absolument pas ou elles te font horreur => tu créé un tableau de booleen de 1 à N, alors vrai l'élement appartient à la solution, faux sinon.

Voilà en tout cas comment traduire ce que j'ai marqué...

Bonne continuation

Bon problème

Super intéressant et difficile !
Cela sent en effet le récursif, mais il s'agirait d'une récursivité profonde et multiple. J'ai commencé à checher mais en vain.
Donc retour à l'itératif.
On part de la solution des 45 unités.1+1+....+1
On cherche à construire les décompositions en 44 termes
Il faut prendre le 1 de la queue (terminal) et l'avancer. La seule solution consiste à le mettre sur premier élement si on veut conserver le sens de variation.
donc 2+1+....+1 à l'exclusion de toute autre possibilité.
Et on continue...
sur 43 éléments il faut à nouveau saupoudrer le 1 final sur les 43 positions possibles. Cette fois on a deux possibilités: soit le mettre sur l'élément de tête, soit sur le deuxième:
3+1+ +1+.......................+1
2+2+1+...+1
Ainsi les solutions sur 45 positions servent à construire celles sur 44 positions
lesquelles servent à leur tour à construire celles sur 43 et ainsi de suite, par la technique que j'intitule le 'saupoudrage du 1'. Mais le processus s'arrête quand on trouve un ensemble de solutions dont le plus petit élément n'est pas 1.
Dès lors la technique de 'saupoudrage' devient difficile, parce que pour une unité c'est simple, il suffit de la 'ballader' sur le tableau et de la lâcher partout où c'est possible, mais avec 2 ou 3 c'est différent, et je ne sais pas comment faire.
Ma technique peut être itérée seulement 37 fois.
Evidemment on peut aussi partir en sens inverse, comme vous le suggérez

45
44 1
43 2

23 22

43 1 1
42 2 1
41 3 1
41 2 2

Je vous passe le code de mon algo en python. Il fournit une quantité impressionante de solutions, mais malheureusement pas toutes. C'est en somme une technique duale, consistant à dilater la somme alors que la mienne consiste à la contracter.
Quand j'aurai un peu de temps j'essaierai encore, bonne chance !
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 # -*- coding: cp1252 -*- # décomposer 45 import copy SOL=[] for i in range (0,45): SOL.append([]) L0=[1]*45 SOL[0]=[L0] def processdec1 (k): T=copy.deepcopy(SOL[k]) SK=[] for i in range(0,len(T)): L=T[i] if L[44-k]>1: print k return L.pop() for j in range (0,44-k): M=copy.deepcopy(L) M[j]=M[j]+1 if (j>0) and M[j-1]<M[j]: break else: if M not in SK: SK.append(M) SOL[k+1]=SK return def processdec (): for k in range(0,38): processdec1(k) return processdec()

05/12/2006, 16h05
Nemerle

La solution de ce problème classique est "simple" une fois qu'on fait quelques exemples à la main.

Toute décomposition comporte de 1 (45=45) à 45 chiffres (45=1+1+...+1).

Trouvons toutes les décompositions à n chiffres 45=x1+...+xn. Pour ce faire, utilisons l'ordre
x1>=x2>=x3...>=xn.
Il est clair que
x1<=45-n+1, x2<=45-x1-n+2, x3<=45-x1-x2-n+3,... soit xi<= 45-(x1-x2-...-x(i-1))-n+i.
En effet si xi est supérieur à cette valeur, même en faisant x(i+1)=1,...,xn=1 on dépasse 45 !! Regardons quelques exemples

Cas n=2:

44 1
43 2
42 3
...

Cas n=3

43 1 1
42 2 1
41 3 1
41 2 2
40 4 1
40 3 2
39 5 1
39 4 2
39 3 3
...

Tu vois quand que tu passes de x1=42 à x1=41, tu fais x2=45-x1-(i-2)=3 et x3=45-x1-x2-(i-3)=1. L'étape suivante tu peux faire x3<-x3+1 entrainant x2<-x2-1, mais dans ce cas x3=x2, c'est fini.

De même, quand tu passes de x1=40 à x1=39, tu fais
- x1=39, x2=45-x1-(i-2)=5, x3=45-x1-x2-(i-3)=1
- x3=1 te permet de passer à x3=2 donc x2=4 (on a x2>x3)
- x3=3 te permet de passer à x3=3 donc x2=3 (on a x2=x3), c'est fini

JE RESUME: pour déterminer toutes les decompositions 45=x1+...+xn, pour un n donné,

- tu commences par x1=45-i+1 et x2=x3=...=xn=1
- A une étape donnée ou la précédente décomposition calculée est x1+...+xn,
- tu vérifies si x(n-1)-1>=x(n)+1: si oui, tu fais x(n)<-x(n)+1 et x(n-1)<-x(n-1)-1
- si non, tu vérifies si (n-2>0 ET x(n-2)-1>=x(n-1)+1 ET x(n-1)+1<=45-x1-x2-...-x(n-2)-n+(n-1) (cf. la formule du début): si c'est ok, tu fais alors x(n-2)<-x(n-2)-1, x(n-1)<-x(n-1)+1 et x(n)=45-x1-x2-...-x(n-1)
- si non, tu vérifies (n-3>0 ET x(n-3)-1>=x(n-2)+1 ET x(n-2)+1<=45-x1-x2-...-x(n-3)-n+(n-2).... ETC...

Avec ça tu dois pouvoir produire ton algo. Je te laisse chercher un peu et te filerai l'algo dans quelques jours. Tu ne dois pas coder "en dur" les n "si alors" de test, il te faut utiliser une variable qui te permet de repérer à chaque étape ou tu tente d'ajouter 1. Ton algo s'arrete quand x1<x2.

Je pense que c'est bon

Voilà, je crois que je n'étais pas loin de la vérité. La méthode était bonne mais il fallait procéder en expansion, plutôt qu'en contraction. On trouve 28482 solutions. Je les ai dans un fichier texte "decomp45.txt". Je peux vous le faire parvenir si vous me dîtes comment.
Voici le source si vous voulez l'exécuter, le vérifier et déboguer si nécessaire.
Z

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# -*- coding: cp1252 -*-
# décomposer 45
import copy
 
SOL=[] # contiendra l'ensemble des solutions
for i in range (0,46):
    SOL.append([]) # liste vide partout pour commencer
 
SOL[0]=[] #pour le total 0
SOL[1]=[[1]] #pour le total 1
 
# la récurrence est amorcée
# on va pouvoir y aller
 
#construit les solutions pour k+1 à partir de celles pour k
def processdec1 (k):
    print k #pour voir la progression
    T=copy.deepcopy(SOL[k]) # récupérer les solutions précédentes
    SK=[] # pour recevoir les nouvelles solutions
    for i in range(0,len(T)):
        L=T[i]
        for j in range (0,len(L)):# récupérer les solutions une par une
            M=copy.deepcopy(L)
            M[j]=M[j]+1 # ajout d'une unité
            if (j>0) and M[j-1]<M[j]: #pour conserver la décroissance
                break
            else:
                if M not in SK: # s'il s'agit d'une nouvelle possibilité
                    SK.append(M) # l'ajouter à celles trouvées précédemment
    SK.append([1]*(k+1)) # pour finir rien que des 1
    SOL[k+1]=SK # mise à jour en vue du traitement suivant
    return
 
def processdec (): # itération de la fonction précédente
    for k in range(1,45):
        processdec1(k)
    return
 
def sauvesoltofic ():
    f=open("decomp45.txt", 'w')
    for i in range(0, len(SOL[45])):
        L=SOL[45][i]
        for j in range(0, len(L)):
            f.write(str(L[j])+" ")
        f.write("\n")
    f.close()
    return
 
 
processdec()                   
sauvesoltofic()

05/12/2006, 16h08
Nemerle

Citation:

Envoyé par Zavonen

On trouve 28482 solutions.

Désolé, tu ne les as pas toutes, loin de là...

Pour la décomposition de 40, il y en a dejà 37338 !

D'où l'intérêt de faire un algo avant de coder de suite... ;)
06/12/2006, 08h03
Zavonen

Ok

Citation:

Envoyé par Nemerle

Désolé, tu ne les as pas toutes, loin de là...

Pour la décomposition de 40, il y en a dejà 37338 !

D'où l'intérêt de faire un algo avant de coder de suite... ;)

D'accord avec votre résultat.
Programme corrigé
Obligé de partir.
Ce soir calcul avec 45
06/12/2006, 08h27
netsabes

Partitions de 45

Bonjour,

tout d'abord merci à tous. Je vois que le problème était loin d'être simple.
Et pourtant, avec Maxima, il suffit de taper:
integer_partitions(45) pour obtenir les 89134 partitions de 45.

Mais je souhaite les rentrer dans un tableau, et je n'ai pas vraiment envie de réutiliser le résultat de Maxima dans un fichier texte, par pure curisosité. Et puis aussi pour avoir un joli code...

Cordialement,

Netsabes.
06/12/2006, 11h25
ToTo13

Bonjour,

si ces réponses te conviennent, penses à marquer le sujet comme résolu...
06/12/2006, 15h56
thewho

Bonjour,

Citation:

Envoyé par ToTo13

Bonjour,

si ces réponses te conviennent, penses à marquer le sujet comme résolu...

+1

En tour cas, la question de départ précisait :

Citation:

Envoyé par netsabes

En fait, la liste de toutes les possibilités m'irait très bien, même sans algorithme.

Puisque tu les as avec ton logiciel Maxima, normalement ton problème est résolu
06/12/2006, 22h34
netsabes

Résolu

Je les ai toutes avec Maxima, mais ce n'était pas le cas au départ :D

Au tout début, je n'avais aucune idée de comment pratiquer.

Merci encore à tous.

Netsabes.

Code et résultat

Citation:

Envoyé par netsabes

Bonjour,

tout d'abord merci à tous. Je vois que le problème était loin d'être simple.
Et pourtant, avec Maxima, il suffit de taper:
integer_partitions(45) pour obtenir les 89134 partitions de 45.

Mais je souhaite les rentrer dans un tableau, et je n'ai pas vraiment envie de réutiliser le résultat de Maxima dans un fichier texte, par pure curisosité. Et puis aussi pour avoir un joli code...

Cordialement,

Netsabes.

Voilà, Il fallait, changer un 'break' en 'continue' dans mon programme candidat, et améliorer aussi un peu la gestion de la mémoire pour obtenir les 89134 solutions en un temps raisonnable:
Voici le code, le fichier est à votre disposition

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# -*- coding: cp1252 -*-
# décomposer 45
import copy
 
SOL=[] # contiendra l'ensemble des solutions
for i in range (0,46):
    SOL.append([]) # liste vide partout pour commencer
 
SOL[0]=[] #pour le total 0
SOL[1]=[[1]] #pour le total 1
 
# la récurrence est amorcée
# on va pouvoir y aller
 
#construit les solutions pour k à partir de celles pour k
def processdec1 (k):
    T=copy.deepcopy(SOL[k]) # récupérer les solutions précédentes
    SK=[] # pour recevoir les nouvelles solutions
    for i in range(0,len(T)):# récupérer les solutions une par une
        L=T[i]
        for j in range (0,len(L)):
            M=copy.deepcopy(L)
            M[j]=M[j]+1 # ajout d'une unité
            if (j>0) and M[j-1]<M[j]: #pour conserver la décroissance
                continue
            else:
                if M not in SK: # s'il s'agit d'une nouvelle possibilité
                    SK.append(M) # l'ajouter à celles trouvées précédemment
    M=[1]*(k+1)# que des 1 pour finir
    SK.append(M)
    SOL[k+1]=SK # mise à jour en vue du traitement suivant
    print (k+1,":",len(SK))# voir la progression
    if k>1:
        SOL[k-1]=[]#pour libérer la mémoire
    return
 
def processdec (): # itération de la fonction précédente
    for k in range(1,45):
        processdec1(k)
    return
 
def sauvesoltofic (): #sauver sur fichier
    f=open("decomp45.txt", 'w')
    for i in range(0, len(SOL[45])):
        L=SOL[45][i]
        for j in range(0, len(L)):
            f.write(str(L[j])+" ")
        f.write("\n")
    f.close()
    return
 
 
processdec()                   
sauvesoltofic()