Discussion :

[e0x1n]

Bonjour à toutes et à tous,

c'est mon premier post ici, et je me présente à vous pour invoquer la puissante magie d'Internet, en sollicitant la communauté avec un petit casse-tête algorithmique que je n'arrive pas à résoudre.
- Voici les données :

Soit x = 400. Je voudrais générer aléatoirement 10 entiers dont les valeurs seraient comprises entre 20 et 60, et dont la somme totale serait égale à x.
Le but étant de produire plusieurs groupes de 10 nombres différents dont chacune des sommes est égale à x.

J'avoue que je n'arrive même pas à savoir par où commencer... Toutes les méthodes que j'imagine n'aboutissent à rien.
Si quelqu'un parmi vous avait un début de piste pour moi, je lui en serais reconnaissant.
Merci :)

[tbc92]

Tu ne sais pas par où commencer, parce que ton problème est insuffisamment formulé.
Déjà, tu parles de 10 nombres aléatoires ... mais le 10ème n'est pas aléatoire du tout, il est totalement imposé. Et même le 9ème, il a des contraintes. Si la somme des 8 premiers est de 300, il faut que le 9ème soit au moins égal à 40.
Et du coup, on ne respecte plus l'énoncé de départ.

Autre point, tu parles de nombres entre 20 et 60. Si je parle de 'distribution uniforme', ou de 'distribution gaussienne', je ne sais pas si ça te parle. Mais tu n'a pas précisé. Et donc on ne sait pas.

J'imagine que tu travailles avec des nombres entiers.
Dans ce cas, une solution simple à mettre en place, mais longue en temps de traitement, c'est de générer 10 nombres aléatoires entre 20 et 60. Et si la somme donne 400, gagné, on garde cette liste. Sinon, on recommence, aussi longtemps que nécessaire. En gros, tu auras 99% des essais qui partiront à la poubelle.
Mais pour les 1% restants, tu as une méthode de génération qui respecte au mieux tes contraintes. Si tu travailles avec des réels, tu peux adapter l'idée facilement.

[e0x1n]

Merci pour cette réponse, je pense avoir tout ce qu'il me faut pour bosser.
Je travaillerai mieux mes énoncés à l'avenir.

[WhiteCrow]

Bonjour,

En fait avec ce genre de problèmes il faut prendre un peu de recul et ne pas commencer par chercher comment tu génères quelque chose mais chercher plutôt une manière d'approcher le problème pour savoir ce que tu veux. Cela permet d'éviter les problèmes XY.

Tu dis :

Soit x = 400. Je voudrais générer aléatoirement 10 entiers dont les valeurs seraient comprises entre 20 et 60, et dont la somme totale serait égale à x.
Le but étant de produire plusieurs groupes de 10 nombres différents dont chacune des sommes est égale à x.

Là tu décris comment tu voudrais construire un ensemble, mais tu ne décris pas réellement ce que tu voudrais choisir ; le choix «aléatoire» ne se porte pas sur les nombres qui composent un ensemble, mais sur l'ensemble lui-même. Je m'explique : ce que tu veux, si je te comprends bien, c'est choisir aléatoirement un ensemble parmi tous les ensembles composés de 10 entiers compris entre 20 et 60 dont la somme vaut 400.

À partir de là, tu peux aussi réfléchir sur ces ensembles. En effet, un ensemble composé de 10 entiers compris entre 20 et 60 dont la somme vaut 400 est la même chose qu'un ensemble de 10 entiers compris entre 0 et 40 dont la somme vaut 200 auquel on aura ajouté 20 à chaque élément. Du coup on se rapproche d'un problème connu : la partition d'entiers (integer partition).
Comme c'est un problème connu et largement étudié tu pourras bénéficier (peut-être) des algorithmes disponibles pour ou construire de tels ensembles ou en choisir un. Tu auras, par exemple, des algorithmes qui classent ces ensembles (rank) et d'autres qui, à partir d'un rang, construisent un ensemble (unrank).

Donc si on part d'un algorithme qui choisi aléatoirement des nombres pour construire l'ensemble tu vas avoir un espace de recherche de l'ordre de 41¹⁰ éléments (13.422.659.310.152.401), si tu passes par le choix d'une partition de 200 de longueur 10, l'espace de recherche se réduit considérablement, il n'y aura plus que 807.151.588 éléments (quasiment 9 ordres de grandeur) parmi lesquels il y aura aussi des ensembles ne correspondant pas à tous tes critères.

Mais bon, cela va dépendre aussi de tes besoins et de ton envie de creuser le sujet. Il va aussi falloir clarifier s'il s'agit d'ensembles ou de tuples, si tu désires bien avoir une certaine distribution ou si cela t'est égal, etc.

[mach1974]

IL FAUT PRENDRE L'ALGORITHME DU SIMPLEXE SUR WIKIPEDIA

10 variables = 400

Sur ce forum, sous prétexte de pédagogisme, on ne répond plus aux questions... C'est soulant

on aurait pu lui parler aussi des fonctions génératrices pseudo aléatoires pour le partage de connaissance avec une fonction modulo

[Flodelarab]

Bonjour

Mouai. Bof. Tout de suite les grands mots. S'il a toutes les solutions possibles dans un fichier, Une solution par ligne. il tire une ligne au hasard. Fin.
Son script n'est pas obligé de réinventer la roue à chaque exécution.

[wiwaxia]

Bonjour,

Soit x = 400. Je voudrais générer aléatoirement 10 entiers dont les valeurs seraient comprises entre 20 et 60, et dont la somme totale serait égale à x.
Le but étant de produire plusieurs groupes de 10 nombres différents dont chacune des sommes est égale à x.

On peut trouver une réponse simple à l'énoncé en lui donnant une interprétation géométrique.

Il s'agit de trouver 10 nombres (p_i) vérifiant

∑(p_i) = 400 et 20 ≤ p_i ≤ 60 ,

donc 10 nombres (q_i) reliés aux précédents par la relation

p_i = q_i + 40

et vérifiant pour leur part:

∑(q_i) = 0 et -20 ≤ p_i ≤ 20 .

On envisage par conséquent 10 vecteurs constants (OM_i) de même norme (R) et de résultante nulle, vérifiant par conséquent:

∑(OM_i) = 0 (vecteur nul) et ║OM_i]║ = R

ainsi qu'un point aléatoire situé à la distance (R) de l'origine du repère, et soumis quand à lui à la condition:

║OM║ = R .

Les produits scalaires correspondants q_i = (OM│OM_i) = R²Cos(θ_i)
vérifient bien les conditions attendues si l'on prend R = 20^1/2 :

∑(q_i) = ∑(OM│OM_i) = OM│∑(OM_i) = OM│0 = 0 , -R² = -20 ≤ q_i ≤ R² = 20 .

# Pour ce qui est de l'aspect aléatoire, on peut travailler
a) en dimension 2 en se basant sur les vecteurs position des sommets d'un décagone régulier inscrit dans le cercle de rayon (R) centré à l'origine (O) du repère, et admettant pour composantes:

OM_i = R*Cos(i*π/5).u_x + R*Sin(i*π/5).u_y ;

on prendra pour le point aléatoire:

OM = R*Cos(θ).u_x + R*Sin(θ).u_y , avec θ = (2π)*Random ;

b) en dimension 3 en partant d'un polyèdre inscrit dans une sphère de rayon (R) centrée en (O), par exemple l'antiprisme à base carrée et à deux faces pointées, l'hexadécaèdre de sommets:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 R      0       0
-R      0       0
 g      0       h
 0      g       h
-g      0       h
 0     -g       h
 g'     g'     -h
-g'     g'     -h
-g'    -g'     -h
 g'    -g'     -h

avec g = (R² - h²)^1/2 et g' = g/2^1/2 ;
Il faudra tirer un point quelconque (M) de la sphère de rayon (R) avec une probabilité surfacique uniforme, par exemple par les instructions:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
REPEAT
  u:= 2*Random - 1; v:= 2*Random - 1; w:= 2*Random - 1;
  s:= Sqr(u) + Sqr(v) + Sqr(w);
UNTIL (0.01 < s) AND (s<1);
  r:= R/Sqrt(s); x:= r*u; y:= r*v; z:= r*w;

Le procédé conduisant à des nombres réels, on pourra passer aux entiers par une fonction d'arrondi; une somme éventuellement non-nulle sera éventuellement corrigée par modification de l'un des termes.

Les maths, ça peut encore servir de temps en temps quoi qu'on dise