Ubuntu-fr

rihegher

forum algorithme pour generer une liste de nombre

Voila mon probleme:

je veux pouvoir generer de facon aleatoire une liste de N entiers dont la somme serait S, ces entiers seraient compris entre MIN et MAX.

N,S,MIN et MAX seraient les parametres de cette fonction, seulement voila j ai reflechi 5 minutes et j ai pas trouvé un moyen simple de coder ca, mais je suis persuadé que quelques mathematicien ou informaticien se sont deja penché sur la question d une telle fonction.

Maintenant je sais que ca a rien a voir avec Ubuntu mais j ai pas trouvé de forum traitant des algorithmes.

alors des idees, des adresses, des suggestions... sont les bienvenues

rihegher

Re : forum algorithme pour generer une liste de nombre

pas d idee?

un ptit up

Val1472

Re : forum algorithme pour generer une liste de nombre

Tu veux generer N nombre entre [MIN,MAX] avec sum(N)=S

M=Max-Min
SumTemp = 0
Pour i allant de 1 a N
  Si SumTemp ==  S+Min
    nombre = 0
  Sinon
    Generation d'un nombre entre [0,M]
  finSi
  SumTemp += nombre juste généré
  Si S+Min-SumTemp<M
    M = S+Min-SumTemp
  FinSi
FinPour
Liste de nombre genere += Min
Premier element liste genere += SumTemp-S

Euh ca doit marcher si mon cerveau n'est pas trop rouillé

Dernière modification par Val1472 (Le 03/11/2005, à 21:25)

etiennez

Re : forum algorithme pour generer une liste de nombre

heu, je crois que tu es rouillé En fait, je ne vois pas comment ton algo peut s'assurer que la somme a bien atteint S.

---

I'm a good boy.

Val1472

Re : forum algorithme pour generer une liste de nombre

Ah c'est une bonne remarque !
J'édite ... Ca devient de plus en plus sale comme solution

rihegher

Re : forum algorithme pour generer une liste de nombre

merci bien, je m attendai a quelque chose de plus mathematiques mais je vais deja essayer ca

etiennez

Re : forum algorithme pour generer une liste de nombre

Val> ça me semble encore buggé (notament, si tu ajoutes le manque au premier chiffre, tu ne t'assure pas de ne pas dépasser Max)

Moi j'ai ça:

fonction genListe(n, s, min, max)
    n_restant = n
    liste = ()
    tant que n_restant > 0
        si n_restant * max < s - somme(liste) alors
            si longueur(liste) == 0 alors
                erreur "pas de solution"
            sinon
                min = liste.pop()
                min = min + 1
                n_restant = n_restant + 1
            finsi
        finsi
        si n_restant * min > s-somme(liste) alors
            si longueur(liste) == 0 alors
                erreur "pas de solution"
            sinon
                max = liste.pop()
                max = max - 1
                n_restant = n_restant + 1
            finsi
        finsi
        si n_restant == 1 alors
            liste.ajouter(s-somme(liste))
            n_restant = 0
        sinon
            liste.ajouter(entier_aleatoire(min, max))
            n_restant = n_restant - 1
        finsi
    fintant
    retoune liste

Mais ça a des défauts, outre que ce ne soit surement pas des plus efficace, le fait que ça ne tente pas d'étaler les valeurs, ce qui fait que dans de certain cas, tu as de grandes chances de te retrouver avec une liste de type (des grand nombres, min, min, min, min, min, etc), ou (des petits nombre, max, max, max, max, max, max, etc) Une solution simple pour limiter cet effet est de borner symétriquement autour de la valeur moyenne (S/N), en ajustant min ou max au debut de la fonction mais c'est tricher sur l'énoncé.
Enfin aprés ça dépends de ce que tu veux faire avec ces chiffres.

---

I'm a good boy.

Black_pignouf

Re : forum algorithme pour generer une liste de nombre

Un peu de pédagogie d'abord, avec une méthode pour construire une montagne d'altitude moyenne S/N :

on crée d'abord un plateau horizontal d'altitude S/N et longueur N
on y fout le bordel en y creusant des trous un peu partout et en récuperant toute la terre pour faire des pics.
mais on creuse pas plus bas que MIN, et on construit pas de pics plus hauts que MAX
voilà!

En code approximatif :

créer une liste de (x1,...,xn) tous égaux à S/N

//NB : Le problème est résolu pour un cas particulier. ;-)
//si ca ne te convient pas, voilà la suite :

créer une liste de (y1,...,yn) aléatoires, pris entre 0 et 1
calculer la moyenne m de ces yi
enlever m à tous les yi

//on obtient une liste dont la somme est nulle
//on pourra toujours la multiplier par quoi que ce soit, puis la sommer aux xi, ca ne changera pas la somme des xi, égale à S

multiplier les yi par le plus petit des 2 nombres (Max-S/N,S/N-min)
 
sommer les yi aux xi

Voilà, on obtient une liste aléatoire de longueur N, dont la somme vaut S et comprise entre MIN et MAX.
Cette solution n'est pas optimale non plus car elle ne remplit qu'une partie de l'intervalle MIN; MAX. Si S/N est proche de Min ou de Max, les nombres vont se cantonner dans un petit intervalle (mais si S/N est la moyenne de Min et de Max, pas de problème). J´y réfléchi et je reviens

Dernière modification par Black_pignouf (Le 04/11/2005, à 15:21)

rihegher

Re : forum algorithme pour generer une liste de nombre

bon tout d abord merci a tous pour l interet porter a cet algo,

en me basant sur l'idee de Black_pignouf et en faisant ca en python ca me donne quelque chose comme ca:

import sys
from random import randrange

##################
####parametres####
##################
nombre=52
somme=460
minimum=2.1
maximum=19.3
force=1000
##################
####          ####
##################


som1=somme*10
min1=minimum*10
max1=maximum*10


#####calcul de la moyenne######
first=som1 % (nombre-1)
moyenne=(som1-first)/(nombre-1)

graine=moyenne-min1
liste = []
liste.append(first)

for i in range(nombre-1):
	liste.append(moyenne)




######melange aleatoire########
Nbtemp=randrange(graine)


liste[0]=liste[0]+min1

elem1=randrange(len(liste))
while((liste[elem1]-min1)<min1):
	elem1=randrange(len(liste))
else:
	liste[elem1]=liste[elem1]-min1


for i in range(force):
	Nbtemp=randrange(graine)
	elem1=randrange(len(liste))

	while((liste[elem1]-Nbtemp)<min1):
		elem1=randrange(len(liste))
	else:
		liste[elem1]=liste[elem1]-Nbtemp

	elem2=randrange(len(liste))

	while((liste[elem2]+Nbtemp)>max1):
		elem2=randrange(len(liste))
	else:
		liste[elem2]=liste[elem2]+Nbtemp



######Ecriture de la liste#####
f = open(sys.argv[1],"w")
for i in liste:
	f.write(str(int(i-(i%10))/10)+ "," +str(int(i)%10)+"\n")
f.write("\n"+str(int(som1-(som1%10))/10)+ "," +str(int(som1)%10)+"\n")
f.close()

voila la force c le nombre de fois qu on brasse le "terrain" ou plutot la liste des nombres,

comme vous le voyez au debut je fais en sorte d avoir une moyenne a peu pres ronde en faisant un modulo de la somme par N-1

et je dois dire que ca marche bien.

je suis novice en python mais j avoue que c assez simple a utiliser.

voila le resultat vas dans un fichier dont le nom est renseigne au lancement du programme (de type csv afin d etre lisible dans un tableur)

merci encore

le code est reutilisable et open source of course