Discussion :

[alain57]

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

[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.

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 :
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).

[alain57]

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

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

c'est deja le cas

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 :

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

[*]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

[Zavonen]

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

Code python :

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

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

[alain57]

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

Code python :

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

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 ?

[pseudocode]

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

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

?

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

[alain57]

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

?

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

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

[Zavonen]

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

c'est quel language ce code ?

C'est écrit dessus

[pseudocode]

C'est écrit dessus

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

[Zavonen]

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.

[alain57]

nul n'est parfais
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 :

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

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!!!!