Probleme combinatoire
20 messages
- Page 1 sur 1
par PapyRusse » 13 Déc 2013, 03:17
Je commence a entrevoir un principe de solution.
L`algorithme serait le suivant :
- on cree 10 "tiroirs"
- on genere les quintuplets un a un
- on place les triplets de chaque quintuplet dans chacun des tiroirs selon le principe suivant : si le triplet existe deja dans un tiroir on ne marque rien sinon on le place sur un tiroir autre en veillant a equilibrer les "tiroirs"
Je ne sais pas si certains "tiroirs" auront un cardinal tres superieur aux autres.
A suivre donc...
L`algorithme serait le suivant :
- on cree 10 "tiroirs"
- on genere les quintuplets un a un
- on place les triplets de chaque quintuplet dans chacun des tiroirs selon le principe suivant : si le triplet existe deja dans un tiroir on ne marque rien sinon on le place sur un tiroir autre en veillant a equilibrer les "tiroirs"
Je ne sais pas si certains "tiroirs" auront un cardinal tres superieur aux autres.
A suivre donc...
par PapyRusse » 13 Déc 2013, 15:45
PapyRusse a écrit:Je commence a entrevoir un principe de solution.
L`algorithme serait le suivant :
- on cree 10 "tiroirs"
- on genere les quintuplets un a un
- on place les triplets de chaque quintuplet dans chacun des tiroirs selon le principe suivant : si le triplet existe deja dans un tiroir on ne marque rien sinon on le place sur un tiroir autre en veillant a equilibrer les "tiroirs"
Je ne sais pas si certains "tiroirs" auront un cardinal tres superieur aux autres.
A suivre donc...
Principe de solution errone.
Cela devrait etre bien plus complexe.
Je laisse decanter 2 ou 3 jours.
par PapyRusse » 13 Déc 2013, 18:29
Pas moyen de creer 10 tiroirs.
En revanche on peut partitionner les 816 triplets en 4 tiroirs (avec redondance).
Quelque soit le tirage d`un quintuplet parmi 18, on aurait quelque soit le tiroir choisi au minimum un triplet.
Chaque tiroir contiendrait au plus 336 triplets.
Ameliorable, je pense.
En principe avec 168 triplets, on est assure d`avoir au moins un triplet quelque soit le quintuplet tire.
L`ideal serait que chaque tiroir contienne aux alentours de 204 triplets (plus ou moins 10%) SANS REDONDANCE.
Encore du boulot a abattre.
En revanche on peut partitionner les 816 triplets en 4 tiroirs (avec redondance).
Quelque soit le tirage d`un quintuplet parmi 18, on aurait quelque soit le tiroir choisi au minimum un triplet.
Chaque tiroir contiendrait au plus 336 triplets.
Ameliorable, je pense.
En principe avec 168 triplets, on est assure d`avoir au moins un triplet quelque soit le quintuplet tire.
L`ideal serait que chaque tiroir contienne aux alentours de 204 triplets (plus ou moins 10%) SANS REDONDANCE.
Encore du boulot a abattre.
par Ben314 » 13 Déc 2013, 18:32
Salut,
On considérons un "quintuplet" {1,2,3,a,b} (en fait, c'est plutôt un ensemble à 5 éléments vu que l'ordre ne compte pas, mais comme "quintuplet est plus court à écrire...) avec a,b distincts >3.
Chacun des 10 "triplets" (même remarque) du quintuplet doit être dans un et un seul de E(i).
Considérons maintenant un triplet fixé {a,b,c} où c est distinct de 1,2,3,a,b.
Ce triplet fait parti de tout les quintuplets {x,y,a,b,c} où x et y sont deux éléments distincts parmi 1,2,3.
Or ce quintuplet contient déjà les triplets {x,a,b} , {x,y,a} et {x,y,b}.
Donc le triplet {a,b,c} ne peut pas appartenir au même E(i) que {x,a,b} ni que {x,y,a} ni que {x,y,b} et ceci quelque soient les x et y distincts parmis 1,2,3.
Or il y a trois triplets de la forme {x,a,b}, trois autres différents de la forme {x,y,a} et encore 3 autres différents de la forme {x,y,b}.
Celà ne laisse pas le choix : le triplet {a,b,c} doit forcément appartenir au même E(i) que le seul triplet non cité parmi les 9 sous-triplets de {1,2,3,a,b} cités çi-dessus, c'est à dire le triplet {1,2,3}.
Sauf que cela signifie que, les triplets {3,4,5} et {3,4,6} doivent tout les deux être dans le même E(i) que {1,2,3} ce qui ne se peut vu qu'ils font tout les deux parti du quintuplet {2,3,4,5,6}.
Il me semble qu'on tombe trés vite sur une contradiction.PapyRusse a écrit:L`objectif est de partitionner les 816 triplets en 10 sous-ensembles de cardinal plus ou moins equivalent (E(i) avec i variant de 1 a 10) tel que quelque soit le quintuplet tire, chacun des sous-ensembles E(i) contienne exactement un triplet.
On considérons un "quintuplet" {1,2,3,a,b} (en fait, c'est plutôt un ensemble à 5 éléments vu que l'ordre ne compte pas, mais comme "quintuplet est plus court à écrire...) avec a,b distincts >3.
Chacun des 10 "triplets" (même remarque) du quintuplet doit être dans un et un seul de E(i).
Considérons maintenant un triplet fixé {a,b,c} où c est distinct de 1,2,3,a,b.
Ce triplet fait parti de tout les quintuplets {x,y,a,b,c} où x et y sont deux éléments distincts parmi 1,2,3.
Or ce quintuplet contient déjà les triplets {x,a,b} , {x,y,a} et {x,y,b}.
Donc le triplet {a,b,c} ne peut pas appartenir au même E(i) que {x,a,b} ni que {x,y,a} ni que {x,y,b} et ceci quelque soient les x et y distincts parmis 1,2,3.
Or il y a trois triplets de la forme {x,a,b}, trois autres différents de la forme {x,y,a} et encore 3 autres différents de la forme {x,y,b}.
Celà ne laisse pas le choix : le triplet {a,b,c} doit forcément appartenir au même E(i) que le seul triplet non cité parmi les 9 sous-triplets de {1,2,3,a,b} cités çi-dessus, c'est à dire le triplet {1,2,3}.
Sauf que cela signifie que, les triplets {3,4,5} et {3,4,6} doivent tout les deux être dans le même E(i) que {1,2,3} ce qui ne se peut vu qu'ils font tout les deux parti du quintuplet {2,3,4,5,6}.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
par PapyRusse » 13 Déc 2013, 19:48
Merci pour ces precisions. Je me suis heurte a cette contradiction malheureusement.
Vu ce que je cherche, j`ai certainement mal formule mon probleme et j`en suis desole.
Le plus simple serait de partitionner dans un premier temps les 816 triplets en 2 sous-ensembles tels que quelque soit le quintuplet tire on ait 5 triplets dans l`un des 2 sous-ensembles et 5 dans l`autre ou au pire une repartition 6/4 ou 4/6.
Serait-ce possible?
Vu ce que je cherche, j`ai certainement mal formule mon probleme et j`en suis desole.
Le plus simple serait de partitionner dans un premier temps les 816 triplets en 2 sous-ensembles tels que quelque soit le quintuplet tire on ait 5 triplets dans l`un des 2 sous-ensembles et 5 dans l`autre ou au pire une repartition 6/4 ou 4/6.
Serait-ce possible?
par Ben314 » 13 Déc 2013, 20:01
Pour du 5/5 à tout les coups, j'ai peur qu'on se heurte de nouveau rapidement à une contradiction théorique (à vérifier...)PapyRusse a écrit:Merci pour ces precisions. Je me suis heurte a cette contradiction malheureusement.
Vu ce que je cherche, j`ai certainement mal formule mon probleme et j`en suis desole.
Le plus simple serait de partitionner dans un premier temps les 816 triplets en 2 sous-ensembles tels que quelque soit le quintuplet tire on ait 5 triplets dans l`un des 2 sous-ensembles et 5 dans l`autre ou au pire une repartition 6/4 ou 4/6.
Serait-ce possible?
Aprés, si on accepte quelques cas à 4/6, c'est sans doute jouable, mais ça risque de ne pas être façile de trouver comment minimiser le nombre de cas 4/6...
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
par PapyRusse » 13 Déc 2013, 20:20
J`ai reussi a creer10 sous-ensembles (tiroirs) de 560 triplets ou on a au moins 1 triplet dans chacun d`eux quelque soit le quintuplet tire. La redondance est forte (560*10=5600 compare a 816 c`est pas ce que je cherche).
Je cherche une solution optimale qui reduit la taille des 10 sous-ensembles a 200 au plus.
Je devrais aborder une autre piste je pense.
On verra demain ....
Je cherche une solution optimale qui reduit la taille des 10 sous-ensembles a 200 au plus.
Je devrais aborder une autre piste je pense.
On verra demain ....
par PapyRusse » 14 Déc 2013, 16:01
Je pense etre sur la bonne piste.
En partitionnant au hasard les 816 triplets en 2, j`obtiens une repartition 5-5,6-4,4-6 dans 2 cas 3 quelque soit le quintuplet tire.
Il y a moyen d`ameliorer ce taux en "swappant" 1 element appartenant au sous ensemble E(1) avec 1 autre de E(2).
100% me semble difficile a atteindre.
En partitionnant au hasard les 816 triplets en 2, j`obtiens une repartition 5-5,6-4,4-6 dans 2 cas 3 quelque soit le quintuplet tire.
Il y a moyen d`ameliorer ce taux en "swappant" 1 element appartenant au sous ensemble E(1) avec 1 autre de E(2).
100% me semble difficile a atteindre.
par Ben314 » 14 Déc 2013, 16:19
Sauf erreur, exactement le même argument que ci dessus montre que tu ne peut pas partitionner les 816 "triplets" en deux de façon à ce que chaque quintuplet donne exactement 5 triplet dans chacun des deux termes de la partition.
Par contre, je ne vois pas de façon immédiate quel est le min des cas "4/6" qu'on doit accepter pour que ce soit réalisable.
Par contre, je ne vois pas de façon immédiate quel est le min des cas "4/6" qu'on doit accepter pour que ce soit réalisable.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
par PapyRusse » 14 Déc 2013, 16:45
Cela reste faisable a la condition que certains triplets fassent partie des 2 sous-ensembles.
On aurait 2 sous-ensembles dont les cardinaux seraient legerement > a 408.
Partitionner les 816 triplets et que ceux-la me semble impossible en raison de la contradiction soulevee plus haut par toi-meme.
A titre d`exemple :
1-2-3-4-5 donnerait pour 1-2-3-4 quatre triplets 1-2-3,1-2-4,1-3-4 et 2-3-4 et pour 2-3-4-5 quatre egalement avec repetition de 2-3-4
Il y en a 10 en tout on aurait le minimum de 4 respecte.
On aurait 2 sous-ensembles dont les cardinaux seraient legerement > a 408.
Partitionner les 816 triplets et que ceux-la me semble impossible en raison de la contradiction soulevee plus haut par toi-meme.
A titre d`exemple :
1-2-3-4-5 donnerait pour 1-2-3-4 quatre triplets 1-2-3,1-2-4,1-3-4 et 2-3-4 et pour 2-3-4-5 quatre egalement avec repetition de 2-3-4
Il y en a 10 en tout on aurait le minimum de 4 respecte.
par PapyRusse » 14 Déc 2013, 18:06
C`est gagne!!!
On peut reussir le 5/5.
Je viens de faire un test plus reduit et donc facilement analysable.
J`ai trouve l`astuce et elle est vraiment simple.
On peut developper un algorithme qui, en moins d`une seconde, peut solutionner le probleme pour un n=100 ou plus au lieu de 18.
On peut reussir le 5/5.
Je viens de faire un test plus reduit et donc facilement analysable.
J`ai trouve l`astuce et elle est vraiment simple.
On peut developper un algorithme qui, en moins d`une seconde, peut solutionner le probleme pour un n=100 ou plus au lieu de 18.
par PapyRusse » 14 Déc 2013, 18:09
On tire 5 parmi 6.
On a une repartition 5/5 pour les 2 sous-ensembles suivants :
E(1)
4 5 6
1 2 3
3 5 6
1 2 4
2 3 4
1 5 6
1 2 6
3 4 5
2 5 6
1 3 4
E(2)
1 3 5
2 4 6
1 3 6
2 4 5
1 4 6
1 2 5
2 3 5
2 3 6
3 4 6
1 4 5
Quelque soit l`un des 6 tirages C(6,5), on a TOUJOURS une repartition 5/5
On a une repartition 5/5 pour les 2 sous-ensembles suivants :
E(1)
4 5 6
1 2 3
3 5 6
1 2 4
2 3 4
1 5 6
1 2 6
3 4 5
2 5 6
1 3 4
E(2)
1 3 5
2 4 6
1 3 6
2 4 5
1 4 6
1 2 5
2 3 5
2 3 6
3 4 6
1 4 5
Quelque soit l`un des 6 tirages C(6,5), on a TOUJOURS une repartition 5/5
par Ben314 » 14 Déc 2013, 20:02
Effectivement, dans le cas où on partitionne en moins de 10, l'argument çi dessus ne tient plus vu que pour obtenir les 9 cas à exclure il faut changer de x et de y (i.e. changer de quintuplet)Ben314 a écrit:Or ce quintuplet contient déjà les triplets {x,a,b} , {x,y,a} et {x,y,b}.
Donc le triplet {a,b,c} ne peut pas appartenir au même E(i) que {x,a,b} ni que {x,y,a} ni que {x,y,b} et ceci quelque soient les x et y distincts parmi 1,2,3.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
par fatal_error » 15 Déc 2013, 11:14
slt,
on pourrait envisager une solution en PLNE
considérons la matrice A:
a_11, a_12, ..., a_1t,
...
a_c1, a_c2, ..., a_ct,
où t représente le nombre de triplets
et c représente le nombre de queues. (les E(i))
Le coeff a_ij dit si le triplet j est présent dans la queue i
on pose M la matrice des quintuplets
m_11,...,m_1n,
...
m_t1,...,m_tn
le coeff m_ij dit si le quintuplet j génére le triplet i
Si on prend le produit AM, on obtient une matrice Q, de coeffs q_cn
q_cn > 0 signifie que le quintuplet n génère (au moins) un triplet qui est présent dans la queue c
### Les contraintes ###
1) tout quintuplet génère un triplet qui est au moins présent dans chaque queue
AM>0 pour tous les coeffs de (AM)
2) chaque triplet est présent en 0 ou 1 exemplaire dans chaque queue
0= 1
(chaque triplet est au moins présent dans une des queue)
### L'heuristique ###
minimiser somme(a_ij)
Il faudrait montrer que la solution générée va donner des queues de taille semblable.
Ce qui n'est pas sûr, mais qui sent bon.
on pourrait envisager une solution en PLNE
considérons la matrice A:
a_11, a_12, ..., a_1t,
...
a_c1, a_c2, ..., a_ct,
où t représente le nombre de triplets
et c représente le nombre de queues. (les E(i))
Le coeff a_ij dit si le triplet j est présent dans la queue i
on pose M la matrice des quintuplets
m_11,...,m_1n,
...
m_t1,...,m_tn
le coeff m_ij dit si le quintuplet j génére le triplet i
Si on prend le produit AM, on obtient une matrice Q, de coeffs q_cn
q_cn > 0 signifie que le quintuplet n génère (au moins) un triplet qui est présent dans la queue c
### Les contraintes ###
1) tout quintuplet génère un triplet qui est au moins présent dans chaque queue
AM>0 pour tous les coeffs de (AM)
2) chaque triplet est présent en 0 ou 1 exemplaire dans chaque queue
0= 1
(chaque triplet est au moins présent dans une des queue)
### L'heuristique ###
minimiser somme(a_ij)
Il faudrait montrer que la solution générée va donner des queues de taille semblable.
Ce qui n'est pas sûr, mais qui sent bon.
la vie est une fête 
par PapyRusse » 15 Déc 2013, 13:17
Merci.
Une donnee inconnue : comment savoir si a_ij est egal a zero ou un si on ignore le contenu des sous ensembles E(i)?
Le probleme est bien plus complexe je pense.
Un essai avec n=9 au lieu de 18 les autres hypotheses demeurant les memes : on tire un quintuplet et on cherche a partitionner E en 2 (pas plus).
J`aimerai bien voir la solution en 5/5.
Je suis sur une solution possible, mais je n`ai pas encore fini.
Une donnee inconnue : comment savoir si a_ij est egal a zero ou un si on ignore le contenu des sous ensembles E(i)?
Le probleme est bien plus complexe je pense.
Un essai avec n=9 au lieu de 18 les autres hypotheses demeurant les memes : on tire un quintuplet et on cherche a partitionner E en 2 (pas plus).
J`aimerai bien voir la solution en 5/5.
Je suis sur une solution possible, mais je n`ai pas encore fini.
par fatal_error » 15 Déc 2013, 13:27
Une donnee inconnue : comment savoir si a_ij est egal a zero ou un si on ignore le contenu des sous ensembles E(i)?
la PLNE appliquée dans ce cas-ci vise à déterminer les coeffs a_ij...
la vie est une fête
par PapyRusse » 15 Déc 2013, 13:33
fatal_error a écrit:la PLNE appliquée dans ce cas-ci vise à déterminer les coeffs a_ij...
Comment calculer les a_ij alors que tu ne connait pas le contenu des E(i)?
Ce sont les E(i) que l`on cherche a definir et pas a_ij?
par fatal_error » 15 Déc 2013, 13:39
si tu lis plus attentivement (...)
a_11, a_12, ..., a_1t, définit E(1)
a_21, a_22, ..., a_2t, définit E(2)
etc.
Trouver les a_ij, c'est trouver les E(i).
Considères la solution que je propose plus haut comme une boite noire
Maintenant pour pas que tu sois fasciné ya deux inconvénients:
- la formalisation des contraintes ne met pas en avant que les E(i) auront la même taille, pe que c'est implementation dependant, pe que par chance c'est toujours le cas par optimisation avec simplexe, pe pas (il faudrait prouver ce dernier).
- avec beaucoup de quintuplets, ca fait des grosses matrices, et pe qu'appliquer simplexe montrera qu'on est beaucoup trop longs.
a_11, a_12, ..., a_1t, définit E(1)
a_21, a_22, ..., a_2t, définit E(2)
etc.
Trouver les a_ij, c'est trouver les E(i).
Considères la solution que je propose plus haut comme une boite noire
- Code: Tout sélectionner
->quintuplets [ ]
[ boite noire ]---> a_ij==E(i)
->triplets [ ]
Maintenant pour pas que tu sois fasciné ya deux inconvénients:
- la formalisation des contraintes ne met pas en avant que les E(i) auront la même taille, pe que c'est implementation dependant, pe que par chance c'est toujours le cas par optimisation avec simplexe, pe pas (il faudrait prouver ce dernier).
- avec beaucoup de quintuplets, ca fait des grosses matrices, et pe qu'appliquer simplexe montrera qu'on est beaucoup trop longs.
la vie est une fête
par PapyRusse » 15 Déc 2013, 13:50
Tu peux demarrer avec des E(i) contenant des triplets choisis de maniere aleatoire et les modifier au fur et a mesure en fonction des contraintes imposees.
Sauf que il faudrait prevoir un systeme d`optimisation evitant les cercles vicieux.
Essaie sur n=9 au lieu de 18.
Je suis en train de le faire.
Je commence a comprendre comment fonctionne le systeme : un 5/5 parfait n`est pas exclus (je ne suis pas encore sur).
J`y travaillerai plus tard.
La, je sors en ville.
Sauf que il faudrait prevoir un systeme d`optimisation evitant les cercles vicieux.
Essaie sur n=9 au lieu de 18.
Je suis en train de le faire.
Je commence a comprendre comment fonctionne le systeme : un 5/5 parfait n`est pas exclus (je ne suis pas encore sur).
J`y travaillerai plus tard.
La, je sors en ville.
20 messages
- Page 1 sur 1
Qui est en ligne
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 14 invités
Tu pars déja ?
Fais toi aider gratuitement sur Maths-forum !
Créé un compte en 1 minute et pose ta question dans le forum ;-)
Identification
Pas encore inscrit ?
Ou identifiez-vous :