Discussion :

[Supfire]

Bonjour,

Je suis entrain de coder un logiciel et je bloque sur un algorithme, voici mon problème :
(Je n’utilise pas à certains endroits les termes mathématiques précis cependant j’espère que mon post reste compréhensible)

On a 3 ensembles : A(0;1;2;3;4) ; B(0;4;5;8;9) et C(1;2;3;5;10)

On doit rassembler ces 3 ensembles en 2 ensembles qui contiennent chacun le minimum de nombres possibles.
Si on forme un ensemble avec A et B on obtiendra : (0;1;2;3;4;5;8;9)
Si on forme un ensemble avec A et c on obtiendra : (0;1;2;3;4;5;10)
Si on forme un ensemble avec B et C on obtiendra : (0;1;2;3;4;5;8;9;10)

On voit que l'ensemble formé par A et C contient moins de nombre que les deux autres par conséquent les deux ensembles formées seront telles que :
L'ensemble N°1 sera formé de A et C
L'ensemble N°2 sera formé de B

Résoudre ce problème de tête est relativement simple mais lorsqu’il s’agit de traiter le même problème avec des milliers d’ensemble cela se corse un peu =)
Voila ce que doit faire mon programme :

Objectif :

On a 2048 ensembles contenant chacun 25 entiers naturels allant de 0 à 255.
Le but est de regrouper ces 2048 ensembles en seulement 256 ensembles.
Avec pour condition que chacun des nouveaux ensembles formés contiennent le minimum d'entiers naturels différents.

J’ai deux idées pour traiter ce problème cependant une demande trop de temps de calcul et l’autre me parait pas suffisamment performante, je poste donc ici dans l’espoir que quelqu’un indique une autre façon de traiter ce problème.

Idée 1 :

1) On analyse les nombres qui sont les plus fréquents
2) On choisit les 256 ensembles (A,F,G,H...etc) qui contiennent le plus de ces nombres redondants
3) On compare à A tous les autres ensembles et on détermine quel est l'ensemble B qui a le moins de différence avec A
4) On forme un nouvel ensemble C composé de A et de B
5) On compare C a tous les autres ensembles (sauf A et B) et on détermine quel est l'ensemble D qui a le moins de différence avec C
6) On forme un nouvel ensemble E composé de C et de D

Et on refait cela (2048/256) 8 fois puis ensuite on choisit effectue à nouveau cette étape avec l'ensemble F puis avec l'ensemble G... etc

A la fin on devrait obtenir 256 ensembles qui contiennent chacun le minimum de nombres possibles.

Cependant cette opération nécessite un certain nombre de boucles et vu le nombre d'ensembles de bases (2048) sa risque de prendre un certain temps de calcul.


Idée 2 :

Voici une autre solution qui n'est pas très rigoureuses et ne donne pas de très bon résultat mais est beaucoup plus rapide :

1) On analyse les nombres qui sont les plus fréquents
2) On choisit les 256 ensembles (A,F,G,H...etc) qui contiennent le plus de ces nombres redondants
3) On compare à l'ensemble A tous les autres ensembles et on détermine les 8 qui ont le moins de différence avec A.
4) On forme un ensemble B avec les 8 ensembles trouvés.

Et on effectue cela encore 255 fois avec les autres sous ensembles F puis G, puis H...etc

Je vous remercie à l’avance pour votre aide ainsi que d’avoir lu ce message.

[bouyao]

Une petite idée :

tu construit un ensemble par :

Code :

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

X(i)= les ensembles  contenant la valeur i

on'aura 256 ensembles

X(0),...,X(255)

à voir :
2048 = 2^11
256 = 2^8
8 = 2^4
25 = 5^2

[Caine]

Une idée du côté de l'intersection:

Code :

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

1
2
3
4
5
6
7
 
On a 3 ensembles : A(0;1;2;3;4) ; B(0;4;5;8;9) et C(1;2;3;5;10) 
 
On doit rassembler ces 3 ensembles en 2 ensembles qui contiennent chacun le minimum de nombres possibles. 
Si on forme un ensemble avec A et B on obtiendra : (0;1;2;3;4;5;8;9)    => inter A/B = {0,4} => 2
Si on forme un ensemble avec A et c on obtiendra : (0;1;2;3;4;5;10)     => inter A/C = {1,2,3} => 3
Si on forme un ensemble avec B et C on obtiendra : (0;1;2;3;4;5;8;9;10) => inter B/C = {5} => 1

Le regroupement d'ensemble qui contiendra le moins d'éléments est donc la combinaison qui a le plus d'éléments dans son intersection.

Donc calculer pour chaque combinaison le nombre d'éléments de l'intersection.
Prendre la combinaison ayant la plus grandre intersection,
Prendre l'ensemble d'origine ayant le moins d'éléments.

Pas de meilleure idée à brûle pourpoint