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
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.
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.
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 papapoule . En réponse au message Recherche algorithme de somme de denombrement. É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 papapoule . En réponse au message Recherche algorithme de somme de denombrement. É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: Exo d'école ?
Posté par papapoule . En réponse au message Recherche algorithme de somme de denombrement. É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.
[^] # Re: Pire des cas
Posté par papapoule . En réponse au message Recherche algorithme de somme de denombrement. É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.