Bonjour,
Voilà, mon problème :
J'ai 10 personnes identifies par une couleur de boule.
Chaque personne à 10 boules
Sur chaque boule, un nombre qui n'est pas forcement unique.
On a 10 urnes, chaque personne place 1 boule dans chaque urne. On a donc 10 urnes avec 10 boules de couleurs différentes.
On tire 2 boules par urne.
On doit avoir a la fin du tirage 2 boules de chaque couleur.
Connaissant les nombres inscrits sur chaque boule, je cherche un algorithme qui me donne la plus grosse somme que l'on peut obtenir.
J’espère que j'ai correctement exposé mon problème.
Merci de vos réponse
# IterTools
Posté par alouali (site web personnel) . Évalué à 2.
Regarde du côté du mode IterTools de Python, tu devrais trouver ton bonheur, il y a plein de choses concernant le dénombrement, les permutations…
# Pire des cas
Posté par _kaos_ . Évalué à 3.
Hello,
Ce n'est pas exactement un algorithme, mais ton max correspond à une situation "au pire des cas" : on tire les deux plus grands nombres par personne.
Donc ton maximum, c'est simplement la somme des deux plus grands nombres par personne.
Il ne peut pas y en avoir de plus grand (raisonnement par l'absurde), car cela reviendrait à contredire l'hypothèse initiale que l'on a choisi les deux plus grands par personne. Ce nombre existe puisqu'il peut se réaliser par tirage. C'est donc ton max.
Matricule 23415
[^] # Re: Pire des cas
Posté par arnaudus . Évalué à 3. Dernière modification le 13 juin 2017 à 08:56.
Je ne suis pas sûr d'avoir compris le problème de la même manière que toi, mais je suis d'accord que la réponse est triviale ; le maximum est la somme des deux plus grands nombres appartenant à des personnes différentes.
Mais honnêtement je pense que le problème a été mal exposé ; il dit qu'à la fin, on doit avoir deux boules de chaque couleur, alors que le protocole ne prévoit pas ça (on tire deux boules par urne, on a donc forcément 20 boules, mais ça peut être 10 bleues et 10 rouges, rien n'impose d'avoir deux boules de chaque couleur).
À mon avis, ça n'est pas un problème de programmation, c'est un problème de probabilités avant tout. Qui peut éventuellement se résoudre en listant les permutations si c'est trop complexe pour faire autrement, mais pour le savoir il faudrait que le problème soit exposé correctement.
[^] # Re: Pire des cas
Posté par papapoule . Évalué à 1.
Bonjour arnaudus,
Effectivement dans les contraintes du tirage, on tire deux boules par urne. Si dans les urnes précédentes, on a déjà tiré 2 boules de la même couleur, on doit en tiré une autre.
Je cherche la somme maximale que l'on peut obtenir connaissant à l'avance la répartition des boules
La programmation des permutations est assez simple, mais au vu du nombre de possibilité, il faut plusieurs heures pour obtenir le résultat.
[^] # Re: Pire des cas
Posté par arnaudus . Évalué à 3.
Disons que dans la première urne, on a tiré "bleu - rouge". On passe à la deuxième. Si on tire "vert -jaune", on passe à la troisième. Si par contre on tire "bleu - rouge" (la situation que tu décris comme "on a déja tiré deux boules de la même couleur"), on doit en retirer une : on remet la rouge, par exemple, et on tire une jaune. On se retrouve avec "bleu - rouge - bleu - jaune", c'est bon? Et on passe à la troisième. Ce que je ne comprends pas, c'est qu'il faut se souvenir de toutes les paires de boules, puisqu'on ne peut pas déduire si on a déja tiré la paire ou non. J'ai bien compris?
C'est un problème de tirage avec une contrainte complexe, ça ne me parait pas évident d'évaluer le nombre de permutations comme ça. C'est majoré par 4510, c'est hyper-limite pour une approche en force brute.
[^] # Re: Pire des cas
Posté par papapoule . Évalué à 1.
Bonjour kaos,
Ton raisonnement "au pire des cas" est valable dans le cas où la répartition des nombres est 'idéale', c'est à dire que les 2 max de deux personnes ne soient pas dans la même urne.
Si c'est le cas, quel est alors la somme max que l'on peut avoir ?
Pour le moment, je fais tourner un algorithme qui calcul le nombre de façon de tirer 2 boules parmi 10 (= 45 possibilités) pour chaque personne.
Puis je fait une permutation des possibilités de ses 45 tirages pour 10 personnes (soit 45 exp 10 permutations) en éliminant les tirages où il y a plus de 2 boules par personne.
l'algorithme calcul la somme pour chaque permutation et me sort la somme max.
Au vu du nombre de permutation, il me faut plusieurs heures pour obtenir la somme.
Je cherche si il n'y a pas moyen de faire plus rapidement sachant que l'on connait à l'avance les nombres écrit sur les boules et leurs répartitions dans chaque urne.
[^] # Re: Pire des cas
Posté par _kaos_ . Évalué à 2. Dernière modification le 13 juin 2017 à 09:11.
Salut,
Il est valable quelque soit la répartition.
Je montre (par l'absurde) qu'il y a un majorant au maximum.
Je ne montre pas (à toi de l'exhiber pour t'en convaincre) qu'il y a un minorant au maximum, le choix des deux plus grands maximum par personnes. Petit indice : il "suffit" de trier les 2 premières boules par personne, de les ranger bien adéquoitement dans les urnes et de remplir le reste correctement.
Le minorant = le majorant, CQFD.
Ça se généralise au cas k boules tirées. Le maximum sera toujours la somme des k n meilleures boules par personnes, il suffit de bien les arranger pour le tirage.
La complexité de ton problème chute drastiquement avec ce peu de maths et revient à un tri.
Matricule 23415
[^] # Re: Pire des cas
Posté par papapoule . Évalué à 2.
Au vu des commentaires, j'ai du mal exposer mon problème
Prenons le cas simple de trois personnes :
A : 100,50,10
B : 80,60,55
C : 8,5,2
Prenons la répartition dans les urnes qui est la suivante :
Urne 1 : 50,80,8
Urne 2 : 100,60,5
Urne 3 : 55,10,2
D’après toi, le max serai : 100+50+80+60+8+5 = 303
or ce tirage est impossible car la boules 8 est dans la même urne que les boules 50 et 80 et la boule 5 est dans la même urne que les boules 100 et 60
Dans mon cas, j'ai 10 personnes avec chacune 10 boules
[^] # Re: Pire des cas
Posté par arnaudus . Évalué à 3. Dernière modification le 13 juin 2017 à 09:48.
Bah oui, tu as dit que tu tirais deux boules par urne.
Je confirme, à chaque précision je comprends encore moins. Tu as 10 personnes avec 10 boules, ça fait 100 boules. Chaque personne tire deux boules dans chaque urne, ça fait 200 boules. Y'a comme un problème, non?
[^] # Re: Pire des cas
Posté par guppy . Évalué à 1.
Salut,
Je ne suis pas certain d'avoir bien compris l'énoncé, mais je me lance.
On calcule le max : 100 + 50 + 80 + 60 + 8 + 5 = 303
On vérifie que ce cas est possible, si oui, on a le max. Sinon on calcule le max immédiatement plus petit : 100 + 50 + 80 + 60 + 8 + 2 et on itère.
[^] # Re: Pire des cas
Posté par _kaos_ . Évalué à 1.
Salut,
Dans ma réponse initiale, je ne fais pas de supposition sur la répartition dans les urnes, elle peut être quelconque.
Si la répartition est fixée comme donnée du problème je ne sais pas s'il est simple de calculer le max directement.
Ce qu'on peut dire en tout cas, c'est qu'il sera de toute façon plus petit. C'est peut-être suffisant ?
Matricule 23415
[^] # Re: Pire des cas
Posté par arnaudus . Évalué à 3.
Comme je l'ai écris au dessus, ton problème n'est pas compréhensible. Dans une urne U, il y a 10 boules de couleurs différentes ; il y a en effet 45 combinaisons possibles de deux boules, et c'est tout.
Tu dis qu'il y a 10 personnes, et une couleur par personne. Ensuite, tu évoques un tirage par personne. J'ai l'impression que tes personnes retirent toutes les boules, mais tu comprends que ton truc est incompréhensible?
Si, comme je crois le comprendre, chaque personne retire deux boules dans chaque urne, et que tu fais la somme de ces 20 boules, le score maximum est la somme des deux plus grosses boules de chaque urne. Si le tirage est donné, c'est trivial. Si les boules sont réparties aléatoirement dans les urnes, le max doit simplement être la somme des 20 plus grosses boules, non? Dans tous les cas, le nombre de permutations est probablement trop grand pour être listé (10! ^ 9 ?) ; c'est pas plusieurs heures qu'il te faut, c'est l'éternité.
# Exo d'école ?
Posté par lolop (site web personnel) . Évalué à 4.
Ça y ressemble beaucoup.
Qu'as-tu essayé, quel code, où est-ce que tu coinces ?
Python 3 - Apprendre à programmer dans l'écosystème Python → https://www.dunod.com/EAN/9782100809141
[^] # Re: Exo d'école ?
Posté par papapoule . Évalué à 2.
Bonjour lolop,
Non, ce n'est pas un exo d'école, mais la modélisation d'un problème plus concret.
Je viens juste de répondre au dessus sur ce qui me coince….(Temps pour calculer la somme des 45 exp 10 permutations en éliminant les cas ou il y a plus de 2 boules appartenant à la même personne)
Le programme tourne en python et je suis débutant. Dans mon cas, le code pourrait être simplifier pour augmenter la vitesse d'obtention du résultat, mais c'est le problème de lenteur vient du nombre de possibilité.
Connaissant à l'avance la répartition des boules dans les urnes, il existe sans doute une autre façon d'aborder le problème qui serait moins longue.
# Pas bien compris
Posté par Marotte ⛧ . Évalué à 2.
Je dois louper un truc parce que pour moi c’est simple…
Le max c’est la valeur des deux plus grosses boule × le nombre d’urnes ?
Si chaque personne a ses deux plus grosses boules qui valent respectivement 100 et 90 le max c’est 190×10 ?
En fait dans chaque urne je dois tirer la première boule d’une personne et la deuxième boule d’une autre personne, à chaque fois.
Dit autrement il faut que dans aucune des urnes il y ait deux boules "100" ou deux boules "90", et qu’on tire ces deux boules (100 et 90) à chaque fois ?
Bon il est tard, visiblement je fais une erreur de raisonnement …
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.