Discussion :

[Hazar2014]

Bonjour à tous;
j'essaye de programmer une fonction qui me donne toutes les solutions entières d'une équation à plusieurs variables entières
j'espère que quelqu'un pourra me donner un coup de main
Merci d'avance.

[Matt_Houston]

Qu'as-tu essayé jusqu'à présent ?

[ternel]

Autre question: comment fais-tu sans ordinateur?

[Hazar2014]

Merci pour vos réponses; alors pour la question de Matt_Houston, j'ai pensé à résoudre un système d'équation à plusieurs variables car normalement cette étape contient deux sommes dont une variable est commune exemple :
x1+x2+x3+x4+x5=7
x2+x6+x7+x8+x9=10 normalement y a une infinité de solution si on travaille sur R mais pour mon cas je travaille sur N.
sinon sans ordinateur, pour la question de ternel, je vais par exemple :
7 0 0 0 0
6 1 0 0 0
6 0 1 0 0
6 0 0 1 0
6 0 0 0 1
5 2 0 0 0
5 0 2 0 0

....

Ma première idée était de travailler sur la distribution de la somme de cette façon mais je n'aurai pas toute les combinaisons le problème principale et comment générer toutes les solutions possibles, par exemple j'aurai pas 5 1 1 0 0 j'ai pensé même à la récursivité mais franchement j'ai pas su comment l'appliquer pour cette exemple.

[ternel]

Tu as un ensemble V de variables, avec des domaines de valeurs, tu dois trouver toutes les combinaisons qui vérifie un ensemble C de contraintes.
Il n'y a que deux manières de procéder: soit tu sais construire la liste des solutions en passant directement d'une quelconque à la suivante, soit ce n'est pas le cas.
Si tu le sais, il suffit de coder l'opération "solution suivante".
Sinon, il te faudra parcourir l'ensemble des possibilités en vérifiant si chacune est une solution.

Visiblement, tu es dans la seconde solution.
Si tu as la garantie que les variables sont toutes positives, tu peux trouver une valeur maximale à chacune.
Si tu sait qu'elles sont même strictement positives, tu peux aller encore plus loin.

avec x1+x2+x3+x4+x5=7:
si pour tout i, xi >= 0, tu peux déduire que pour i dans {1,2,3,4,5}, xi <= 7.
si pour tout i, xi > 0, tu peux déduire que pour i dans {1,2,3,4,5}, xi <= 7 - 5 = 2.

tu as aussi toutes les équations sous-jacentes, telles que:

• x2 + x3 + x4 + x5 = 7 - x1
• x3 + x4 + x5 = 7 - x1 - x2
• x4 + x5 = 7 - x1 - x2 - x3
• x5 = 7 - x1 - x2 - x3 - x4

Cela signifie que tu n'as pas besoin de tester toutes les combinaisons. (cas positif)

pour x1 de 0 à 7
    pour x2 de 0 à 7 - x1
        pour x3 de 0 à 7 - x1 - x2
            pour x4 de 0 à 7 - x1 - x2 - x3
                une solution est {x1, x2, x3, x4, (7 - x1 - x2 - x3 - x4)}

A priori, il y a des techniques mathématiques d'optimisation (à base de matrice, je crois). Cherche "système d'équations linéaires"

[Matt_Houston]

Pour que les choses soient bien claires, on parle ici d'équations à plusieurs inconnues, pas d'équations polynomiales ?

Non parce que « x2+x6+x7+x8+x9 » peut prêter à confusion, peut-être faudrait-il écrire « a + b + c + ... » ?

[Hazar2014]

Merci d'avoir détaillé votre réponse mais le problème est la généralisation c'est à dire pour N variables entières et pour n'importe quelle somme donc pour N boucles ce n'est pas évident

[Hazar2014]

j'ai oublié de vous signaler que les variables sont strictement positives.
j'essaye de programmer cette logique :

7 0 0 0
6 1 0 0
6 0 1 0
6 0 0 1
5 2 0 0
5 1 1 0
5 1 0 1
5 0 2 0
5 0 1 1
5 0 0 2
4 3 0 0
4 2 1 0
4 2 0 1
4 1 2 0
4 1 0 2
4 1 1 1
4 1 0 2
4 0 3 0
4 0 2 1
4 0 0 3
3 4 0 0
3 3 1 0
3 3 0 1
3 2 2 0
3 2 1 1
3 2 0 2
3 1 3 0
3 1 2 1
3 1 1 2
3 0 4 0
3 0 3 1
3 0 2 2
3 0 1 3
3 0 0 4
.....
En écrivant et vérifiant cet exemple, je viens d'avoir une idée c'est de jouer sur la position dans la matrice des solutions et non pas sur la somme c'est à dire
la première case [0][0] = la somme ensuite [0][0 à 3]=somme -1; [0][4-9]= somme-2; ou somme =somme-1;
la deuxième colonne à partir du reste de la somme on commence 7-5=2 donc on commence de 2 ensuite 2 de 1 et 3 de 0
je ne sais pas si vous avez a saisir l'idée

[Hazar2014]

Vous avez peut être raison Matt_Houston

[ternel]

En utilisant un vector, c'est largement faisable.
Pour créer une solution a partir d'une autre, il suffit de transférer une unité d'une variable a une autre.
Avec un peu d'ordre, c'est aisé.
Pour tout N, notons P[N](S) = { (x1, ..., xN) | pour tout i 0 <= xi <= S et x1 + x2 + ... + xN = S} l'ensemble des solutions de l'équation.
P[N](S) = {(x1, ... xN) | 0<= xN <= S et (x1, ..., x(N-1)) appartient à P[N-1](S-xN)}.

Si E est un problème de N variable, alors F est un problème de N-1 variables.
Et ainsi de suite jusqu'à tomber sur les problèmes de type P[1](S) qui ont un unique élément. P[1](S) = { (S) }.

P[2](S) = {
(0, S)
(1, S-1)
(2, S-2)
...
(S, 0)
}

Il te suffit donc d'écrire une structure simple pour représenter une solution (à base de std::array ou std::vector), un ensemble de solutions (std::vector<Solution>)
De là, il te suffit d'écrire une fonction qui prenant une taille et une somme te retourne l'ensemble de ses solutions.
Cette fonction s'écrit avec une simple boucle et une récurrence (choisis bien ta condition d'arret)
Ca n'empeche pas que la complexité de la recherche est de l'ordre de S puissance N.

Cela dit, ton problème est plus complexe, parce qu'il utilise plusieurs équations.

[ternel]

Attention, comme le suggère Matt_Houston, si c'est un problème d'équation polynomiale, c'est une toute autre paire de manches.
Dans tous les deux cas, chercher la forme mathématique des solutions est nécessaire. L'ordinateur n'est pas magicien.
Il existe des outils de calculs formels qui pourraient donner la réponse, mais je ne les connais pas précisément.

[Hazar2014]

Il s'agit pas d'équation polynomiale