Recherche algo pour pour résoudre un problème à 4 inconnues

Bonsoir,

Je developpe actuellement un logiciel qui est censé poser des questions au hasard (la n'est pas vraiment le probleme), le soucis est qu'il faut qu'en plus il affiche exactement un nombre X de question pour aillant un total Y de points

on me donne 3 parametres et je dois afficher les questions en fonction


parametre n°1 (il s'agit plutot de constantes)
il existe 4 type de questions
a: des questions à 2 points
b: des questions à 3 points
c: des questions à 4 points
d: des questions à 5 points


parametre n°2 :
ma fonction doit etre appeler avec X le nombre total de questions à afficher (par exemple 8)

parametre n°3:
ma fonction recois comme second paramettre Y le nombre total de points pour la séance de questions (par example 32)


Je recherche donc desespérement un algo qui me permettra de resoudre le probleme plus intelligement que ce qu'a fait un collègue (un random sur une itération de 1 000 000)
ok sa solution fonctionne les 3/4 du temps, mais ca fait mouliner le pc inutilement et ca arrive que ca foire car le million d'itération est dépassé (il a été fixé pour pas attendre indéfiniment)



example concret

ma_fonction(X = 8, Y = 32)
ca me renvera tableau avec par example
4 questions "d" de valeur 5 points
et 4 questions "b" de valeur 3 points

ou alors
1 question "a" de valeur 2 points
5 questions "c" de valeur 4 points
2 questions "d" de valeur 5 points


soit donc bien 8 questions avec exactement 32 points


si quelqu'un à une idée je suis preneur :ccool:

Il y a une amélioration simple à apporter à la méthode de ton collègue qui consiste à regrouper les questions apportant le même nombre de points dans des listes.

1. Ensuite, on tirera aléatoirement des listes (en laissant la possibilité de choisir plusieurs fois une même liste).
2. Si le total convient (et si le nombre d'éléments d'une liste est supérieur ou égal au nombre de fois où la liste a été tirée), Bingo 8-) :
3. Il ne reste plus qu'à faire un random dans chaque liste (en passant à la question de la liste suivant le random si la question correspondante a dèjà été tirée).

Si le nombre de listes est limité, on pourra à la place de l'étape 1) déterminer toutes les combinaisons de listes répondant aux critères X et Y (ainsi qu'à la condition que le nombre d'éléments d'une liste soit supérieur ou égal au nombre de fois où la liste apparait), et choisir une combinaison par tirage aléatoire dans cet ensemble. Ensuite, étape 3).

Citation:

---

Envoyé par alain57

example concret

ma_fonction(X = 8, Y = 32)
ca me renvera tableau avec par example
4 questions "d" de valeur 5 points
et 4 questions "b" de valeur 3 points

ou alors
1 question "a" de valeur 2 points
5 questions "c" de valeur 4 points
2 questions "d" de valeur 5 points


soit donc bien 8 questions avec exactement 32 points

si quelqu'un à une idée je suis preneur :ccool:

---

C'est à dire trouver des entiers positifs ou nuls a,b,c,d tels que

a + b + c + d = 8
a*2 + b*3 + c*4 + d*5 = 32

:koi: ?

Si c'est ça, c'est pas trop dur. La première équation limite beaucoup l'espace de recherche. :D

Citation:

---

Envoyé par Graffito

Il y a une amélioration simple à apporter à la méthode de ton collègue qui consiste à regrouper les questions apportant le même nombre de points dans des listes.

---

en fait les données sont dans une bdd, et j'ai deja une requettes pour avoir toutes les questions puis je trie manuellement le resultat en créant 4 listes qui contiennent toutes les questions correspondante à une valeur
en gros j'ai ca

liste_a => toutes questions à 2 points
...
liste_d => toutes les questions à 5 points

Citation:

---

Envoyé par Graffito

Ensuite, on tirera aléatoirement des listes (en laissant la possibilité de choisir plusieurs fois une même liste).

---

c'est deja le cas

Citation:

---

Envoyé par Graffito

Si le total convient (et si le nombre d'éléments d'une liste est supérieur ou égal au nombre de fois où la liste a été tirée), Bingo 8-) :

---

hum la je vois pas trop ce que tu veux dire ...

Citation:

---

Envoyé par Graffito

[*]Il ne reste plus qu'à faire un random dans chaque liste (en passant à la question de la liste suivant le random si la question correspondante a dèjà été tirée).

---

en fait à chaque fois que je prend un element au hasard d'une de mes 4 listes, je l'enleve de la liste original pour eviter tout doublon

ainsi si l'algo existant choisi un element de type a, la liste_a fournira alors une question au hasard et supprimera la question de son contenu

ps: mes 4 listes sont généré à l'appel de fonction, donc si j'appel ma fonction à nouveau, les 4 listes seront dans leur état original


merci pour la réponse (ca fait plaisir de voir que ya des gens comme moi qui se couchent tard ....), par contre c'est peut etre l'heure ou la fatigue voir la saturation mais je comprends pas trop ton idée

Dans tout langage admettant les 'comprehension lists' cela se programme en une ligne.
Poser le problème c'est le résoudre

Code:

---

1 2 3 4 5 6 7

def Solutions(X,Y): R=range(0,9)#R=[0,1,2,3,4,5,6,7,8] return [(a,b,c,d) for a in R for b in R for c in R for d in R if a+b+c+d==X and 2*a+3*b+4*c+5*d==Y] if __name__ == "__main__": print Solutions(8,32); """Résultat: [(0, 0, 8, 0), (0, 1, 6, 1), (0, 2, 4, 2), (0, 3, 2, 3), (0, 4, 0, 4), (1, 0, 5, 2), (1, 1, 3, 3), (1, 2, 1, 4), (2, 0, 2, 4), (2, 1, 0, 5)]"""

---

Sinon 3 boucles for imbriquées
a varie de 0 à X
b varie de 0 à X-a
c varie de 0 à X-a-b
d prend la valeur X-a-b-c
faire le test 2*a+3*b+4*c+5*d==Y imprimer la soluce si OK

Citation:

---

Envoyé par pseudocode

C'est à dire trouver des entiers positifs ou nuls a,b,c,d tels que

a + b + c + d = 8
a*2 + b*3 + c*4 + d*5 = 32

:koi: ?

Si c'est ça, c'est pas trop dur. La première équation limite beaucoup l'espace de recherche. :D

---

yes une deuxieme réponse ^^
avec un peut de chance j'aurai grace à votre aide la solution lorsque j'irrai bosser
pour cet example concret oui

mais comme indiqué la fonction prend 2 parametres, donc les équations changent .... et le resultat aussi ^^

j'ai tenté de reproduire mes vieux cours de math de systeme d'équation linéaire, mais ça remonte
puis 2 équations à 4 inconnues c'est pas forcement le chéma le plus simple, surtout pour quelqu'un qui était "moyen" en maths

ps: j'ai 2 feuilles A4 rempli de maths, mais je dois mal m'y prendre :calim2:

Citation:

---

Envoyé par Zavonen

Dans tout langage admettant les 'comprehension lists' cela se programme en une ligne.
Poser le problème c'est le résoudre

Code:

---

1 2 3 4 5 6 7

def Solutions(X,Y): R=range(0,9)#R=[0,1,2,3,4,5,6,7,8] return [(a,b,c,d) for a in R for b in R for c in R for d in R if a+b+c+d==X and 2*a+3*b+4*c+5*d==Y] if __name__ == "__main__": print Solutions(8,32); """Résultat: [(0, 0, 8, 0), (0, 1, 6, 1), (0, 2, 4, 2), (0, 3, 2, 3), (0, 4, 0, 4), (1, 0, 5, 2), (1, 1, 3, 3), (1, 2, 1, 4), (2, 0, 2, 4), (2, 1, 0, 5)]"""

---

---

merci me reste plus qu'a transformer ca en ruby :)
par contre je pense qu'il manque un tout petit truc dans l'algo donné
R = range(0, X+1)

ps : au risque de paraitre encore plus ridicule=> c'est quel language ce code ?

Citation:

---

mais comme indiqué la fonction prend 2 parametres, donc les équations changent .... et le resultat aussi ^^

---

Si toutes les équations avaient les mêmes solutions, ça se saurait :mouarf:

Citation:

---

c'est quel language ce code ?

---

C'est écrit dessus

Citation:

---

Envoyé par Zavonen

C'est écrit dessus

---

c'est d'ailleurs marrant de connaitre Ruby mais pas Python.

Il semble que les 'comprehension lists' existent en Ruby:
http://stackoverflow.com/questions/3...ension-in-ruby
Mais avec trois petites boucles toutes simples on s'en sort. C'est moins joli mais (dans ce cas précis) plus efficace.

nul n'est parfais :mouarf:
je prefere les pierres précieuses aux reptiles ^^
j'ai vite fait retranscrit ton code en ruby, bon ya peut etre plus court, mais pour le moment je recherchais simplement d'éviter un algo qui me semblais vraiment idiot......... (faire du random, tester si c'est bon et recommancer au maximum 1 000 000 de fois c'est pas top top

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

def solution(x, y) result = [] r = (0..(x+1)).to_a for a in r do for b in r do for c in r do for d in r do result << "(#{a}, #{b}, #{c}, #{d})" if a+b+c+d==x && 2*a+3*b+4*c+5*d==y end end end end return result end

---

en tout cas GROS merci à vous!!!!

Voir mes indications:
Tu peux réduire les boucles b et c et la boucle d ne sert à rien.
La seule valeur de d susceptible de convenir est X-a-b-c

décidément c'est l'heure de se coucher pour moi

en premier je zap le python
et en deuxieme je zap la fin de ton message....

grace à ton aide je passe d'un algo illogique et lent, à un algo mathématique bien plus rapide

j'ai hate de tester ca dans le projet apres avoir dormis

certaines création de questionnaire duraient pres de 40 secondes sur un serveur de tueur ..... ca me ferai trop plaisir que ca passe à moins d'une seconde :ccool:

Citation:

---

Envoyé par alain57

certaines création de questionnaire duraient pres de 40 secondes sur un serveur de tueur ..... ca me ferai trop plaisir que ca passe à moins d'une seconde :ccool:

---

Attention, l'algo de Zavo donne la liste de TOUTES les combinaisons de questions possibles qui remplissent tes critères.

Si tu as besoin d'une seule solution, tu peux arreter l'algo à la première solution trouvée. Et pour gérer le coté aléatoire de la combinaison, il suffit de mélanger les tableaux de "range" (noté "r" dans ton algo).

Il parait curieux de faire ce calcul à chaque fois.
Calcule d'abord une table 1..nombre max de questions * 1.. nombre max de points où chaque case contient les combinaisons possibles pour x et y

Citation:

---

Envoyé par pseudocode

Attention, l'algo de Zavo donne la liste de TOUTES les combinaisons de questions possibles qui remplissent tes critères.

Si tu as besoin d'une seule solution, tu peux arreter l'algo à la première solution trouvée. Et pour gérer le coté aléatoire de la combinaison, il suffit de mélanger les tableaux de "range" (noté "r" dans ton algo).

---

en fait dans mon cas j'ai bel et bien besoin de toutes les combinaisons
tout simplement parce que le probleme reel est plus complexe

contrairementa à la simplification de mon probleme que j'ai exposé ici, ma fonction fonctionne autrement
elle prend 3 parametres (nombre_de_question, points, possibilite_deja_teste)

d'autre part elle ne genere pas de tableau contenant la somme des valeurs, mais bien les valeurs à proprement dit

donc pas [[0, 0, 8, 0], [0, 1, 6, 1]...]
mais
[[4,4,4,4,4,4,4,4],[3,4,4,4,4,4,4,5],...]

en deuxieme lieu la methode enleve les possibilite deja testé (le tableau comme 3eme parametre)
puis elle prend une possibilité au hasard et mélange le contenu du tableau (pour eviter que les questions soient par la suite toujours affiché par ordre de point)

elle me renvois donc un tableau contenant une seule possibilité
et le programme regarde apres si ca correspond à mes données


par example il se peut que pour une certaine categorie de question il n'y a jamais de question à 5 points

ok c'est vrai que du coup je gaspille encore des ressources car je dis pas explicitement à ma fonction que y pas de question à valeur d=5

mais ca ne représente rien du tout comparé au gaspillage de l'algo original
meme lorsque j'atteinds mes valeurs maximum qui sont 30 questions pour un total de 99 points

sur le serveur la requette originale durait plus de 40 secondes
sur mon pauvre ordi portable, la requette ainsi modifié dure moins de 2 secondes

demain on testera ca sur le nouveau serveur (un xeon avec 16 cores)
le serveur actuel avais que 1 core

Citation:

---

Envoyé par alain57

en fait dans mon cas j'ai bel et bien besoin de toutes les combinaisons
tout simplement parce que le probleme reel est plus complexe

contrairementa à la simplification de mon probleme que j'ai exposé ici, ma fonction fonctionne autrement
elle prend 3 parametres (nombre_de_question, points, possibilite_deja_teste)

d'autre part elle ne genere pas de tableau contenant la somme des valeurs, mais bien les valeurs à proprement dit

donc pas [[0, 0, 8, 0], [0, 1, 6, 1]...]
mais
[[4,4,4,4,4,4,4,4],[3,4,4,4,4,4,4,5],...]

en deuxieme lieu la methode enleve les possibilite deja testé (le tableau comme 3eme parametre)
puis elle prend une possibilité au hasard et mélange le contenu du tableau (pour eviter que les questions soient par la suite toujours affiché par ordre de point)

elle me renvois donc un tableau contenant une seule possibilité
et le programme regarde apres si ca correspond à mes données


par example il se peut que pour une certaine categorie de question il n'y a jamais de question à 5 points

ok c'est vrai que du coup je gaspille encore des ressources car je dis pas explicitement à ma fonction que y pas de question à valeur d=5

mais ca ne représente rien du tout comparé au gaspillage de l'algo original
meme lorsque j'atteinds mes valeurs maximum qui sont 30 questions pour un total de 99 points

sur le serveur la requette originale durait plus de 40 secondes
sur mon pauvre ordi portable, la requette ainsi modifié dure moins de 2 secondes

demain on testera ca sur le nouveau serveur (un xeon avec 16 cores)
le serveur actuel avais que 1 core

---

:evilred:
ce petit programme en Turbo Pascal te calcule toutes les possibilités en moins de 0.2 s avec un Pentium4 à 2.4GHz

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

program combi; uses exten; var a,b,c,d,i,j,k,l,m:integer; jj:longint; begin writeln(lheure); jj:=0; for l:=1 to 30 do for m:=2 to 99 do begin k:=0; for d:=0 to m div 5 do for c:=0 to l-d do for b:=0 to l-c-d do begin a:=l-b-c-d; if 2*a+3*b+4*c+5*d=m then inc(k); end; jj:=jj+k; {writeln(l,' ',m,' ',k,' ',jj);} end; writeln('jj=',jj); writeln(lheure);end.

---

la fonction en elle meme dure pas 2 secondes, je tiens à vous rassurer

Code:

---

1 2 3 4 5 6 7 8 9 10

def mesure a = Time.now Question.get_needed_scores(30,99,[],true) b = Time.now return b-a end end   mesure => 0.034392

---

les trolls pouront toujours dire que ruby 1.8.X et rails 2.3.5 sont lent
mais en fait ce qui prend le plus de temps c'est ce qu'il y a autour de la fonction.... Alors qu'avant c'etait la fonction qui prennais le plus gros temps

en effet pour afficher 1 page internet ya presque toujours plus de 100 requettes SQL 8O8O8O
j'ai déjà enlevé une bonne dixaine de requettes inutiles, mais le projet est complexe, sans compter toutes les erreurs de débutant qu'il contient....

c'est un peu ca, de donner un projet à faire entierement par un stagiaire en info....

du coup je me tappe l'optimisation ,la sécurité et la maintenance sur ce projet

le bon coté des choses, c'est qu'avec toutes les boulettes que je corrige, mon patron arretera de filler des projets à l'aveuglette aux stagiaires sans qu'il y a un superviseur, du moins je l'espere car s'il continue a me filler des trucs pareil en esperant que je fait le magicien .... bah je vais finir par m'ennervé

mais bon quand t'as un chef qui te dit : faut que ca va vite, que le client voit que ca avance, l'optimisation et la sécurité ca peut venir plus tard.... bah :aie::roll: